Vasiljko's blog

By Vasiljko, history, 7 years ago, In English

Given graph with N vertices and M edges. You need to find if there is a way to partition the graph in two parts in such a way that these parts are connected with at least m/2 edges. Division is integer division. If there is solution print it out, else print -1. Input: first two numbers are N and M. Next M lines are pairs of integers (X,Y) representing edge between vertices X and Y. Output: If there is no solution, print -1. Else, in the first line print size of two groups (N1,N2) , in second line print N1 numbers representing vertices in first group, same for second group.

5<= N <= 1000
1<= M <= 10000
TL : 0.2s
ML : 64MB

Input:
8 10
1 2
1 5
1 6
5 6
2 6
3 8
3 7
3 4
4 8
7 8

Output:
4 4
5 6 7 8
1 2 3 4

Your help would be appreciated.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Vasiljko (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you could try to think what happens if you just construct the partitioning node by node?

Spoiler
Spoiler 2
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can i count the number of edges in best time complexity?