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.
Auto comment: topic has been updated by Vasiljko (previous revision, new revision, compare).
Maybe you could try to think what happens if you just construct the partitioning node by node?
Let's assume that you have found a suitable partitioning for subgraph consisting of nodes (X_1, ..., X_k). Let A be the set of nodes in the first group and B the set of nodes in te second group. How could you augment that partitioning with node X_(k+1)?
Count the number of edges from X_(k+1) to A and B. If there are more edges to A, then add X_(k+1) to B. If there are more edges to B, then add X_(k+1) to A.
Now you have partition for subgraph (X_1, ..., X_(k+1)) with at least as many edges between the partitions as within the partitions.
How can i count the number of edges in best time complexity?