Interesting Graph Problem

Revision en3, by Vasiljko, 2017-10-07 22:42:55

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Vasiljko 2017-10-08 11:39:43 9 Tiny change: 'cted with m/2 edges' -> 'cted with at least m/2 edges'
en5 English Vasiljko 2017-10-08 10:53:06 38 Tiny change: ' \n1 2 3 4' -> ' \n1 2 3 4\n\n\nYour help would be appreciated. '
en4 English Vasiljko 2017-10-07 22:43:24 14
en3 English Vasiljko 2017-10-07 22:42:55 57
en2 English Vasiljko 2017-10-07 22:40:30 2 Tiny change: ', print -1; Else, in ' -> ', print -1. Else, in '
en1 English Vasiljko 2017-10-07 22:40:02 878 Initial revision (published)