Link to the question: Contest Page | CodeChef
Given TestCases Explanation:
INPUT :
2
2
1 2
6
1 2
1 3
3 4
3 5
3 6
OUTPUT :
1
1
2
2
1 3 5
2 4 6
Case 1:
No explanation needed
Set 1 : 1
Set 2 : 2
Case 2
for k = 2
Hk edges
Distance 1 :
1 2
1 3
3 4
3 5
3 6
Distance 2 :
1 4
1 5
1 6
2 3
4 5
4 6
5 6
After forming sets
Edges in the good graph (E)
1 2
3 4
3 6
1 4
1 6
2 3
4 5
5 6
** SOLUTION:**
If solution have k = 1
Then for the graph to be connected. Parent of all nodes should be in a different set.
This can be done simply by using a simple DFS function
DFS (int nd,vector<int> adj[],int flag,int par,vector<int> ans[]){
ans[flag].push_back(nd);
if(flag == 0)
flag = 1;
else
flag = 0;
for(int i = 0;i < adj[nd].size();i++){
if(adj[nd][i] != par)
DFS(adj[nd][i],adj,flag,nd,ans);
}
}
If the size of both sets is equal. Then k = 1 and both the sets are an answer.
Special Case
If the graph is a degenerate tree like a graph with edges
1 2
2 3
3 4
4 5
5 6
set u: 1 3 5
set v: 2 4 6
Therefore for a solution, adjacent nodes are put in different sets.
General Case:
For k = 2 having an answer is always possible.
Explanation
Single path of DFS is a degenerate tree
Algorithm used
First, take root node as ND and start moving from ND to a leaf node and keep storing the path (Let it be P).
After reaching the leaf node. Adjacent nodes in P get in different sets.
All the nodes in P are visited and can’t be part of any other path.
If there is any node connected with a visited node and is not visited itself.
Then take that node as ND and clear P.
Move from ND to a leaf node and keep storing the path (Let it be P) which contains only elements which are not visited yet.
After reaching the leaf node our P is completed.
IMPORTANT OBSERVATIONS :
We can start putting elements of P. To U or V any one of them. As suppose ND is connected to
R (the node of the previous path). So If R belongs to U then Child of R or Parent of R belongs to V or vice versa. As k = 2, therefore, ND is connected to R, Child of R and Parent of R. So P would connect to already existing graph always. (therefore for k = 2 answers always exists, k = 2 is maximum possible value of k).
Using the given technique or algorithm Difference between the size of sets would be at max 1.
If the number of elements in P is even then, Adjacent elements of P get in different sets. (any order)
If the number of elements in P is odd and the number of elements of Both the sets are equal then Adjacent elements of P get in different sets. (any order)
If the number of elements in P is odd and the number of elements of Both sets is not equal. Then
ND get in the set with the lesser number of elements and other elements get in sets such that adjacent elements of P are in different sets.
As this would result in Size of U = Size of V.
For example, If the size of U = 3 and size of V = 2 and We have a P with size 3.Then we would Put ND in V( other elements alternatively ).
Resulting in size of U = size of V = 4 finally.
*TAKING EXAMPLE FOR CLARIFICATION OF EXPLANATION : *
Take a graph G with the number of nodes N = 10
Edges of G :
1 2
2 3
3 4
4 5
1 6
6 7
4 8
8 9
9 10
SOLUTION
For k = 2
First, take ND = 1 and Make a Path from 1 to 5 (P = 1 ,2 ,3 ,4 ,5).
Odd position elements get in U and even position elements get in V.
Set U : 1 3 5
Set V : 2 4
Mark 1,2,3,4,5 as visited and Clear P.
Taking ND = 8 ( As it is not visited yet and It is connected to a visited element ‘3’).
Make a Path from 8 to 10, therefore, P = 8 9 10.
As k = 2 therefore 8 is connected with 3,4,5.Therefore If we put odd position elements in U and even position elements in V or vice versa. The Graph would always remain connected.
As P size is odd and size of U is not equal to size of V.
So, Odd position elements get in Set which has a smaller size. (As elements at an odd position are more).
After putting the elements:
set U : 1 3 5 9
set V : 2 4 8 10
Mark 8,9,10 as visited and Clear P.
Taking ND = 6 ( As it is not visited yet and It is connected to a visited element ‘1’).
Make a Path from 6 to 7, therefore, P = 6 7.
As k = 2 therefore 6 is connected with 1,2.Therefore If we put odd position elements in U and even position elements in V or vice versa. The Graph would always remain connected.
As size of P is even, therefore, we can elements in any order alternatively.
After putting the elements :
set U: 1 3 5 9 6
set V: 2 4 8 10 7
Mark 6,7 as visited and
A possible answer is
**2
1 3 5 9 6
2 4 8 10 7**
ACCEPTED CODE:
PLEASE THUMBS UP. If you are able to understand the editorial.
If any doubts/suggestion please put them below. 