Interesting Graph Problem
Difference between en5 and en6, changed 9 character(s)
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. 

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)