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.
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.