You are not logged in. Please login at www.codechef.com to post your questions!

×

GRAPART - UNOFFICIAL EDITORIAL(simpler explanation)

Link to the question: https://www.codechef.com/JAN19A/problems/GRAPART

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:

Solution

PLEASE THUMBS UP. If you are able to understand the editorial.

If any doubts/suggestion please put them below. :)

asked 03 Feb, 14:46

deepanshuvaid7's gravatar image

6★deepanshuvaid7
212
accept rate: 0%

edited 03 Feb, 18:35

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,596
×1,410
×1,219
×726
×247
×109
×13

question asked: 03 Feb, 14:46

question was seen: 327 times

last updated: 03 Feb, 18:35