KGP14C - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PRE-REQUISITES:

Graphs, Graph coloring, BFS

PROBLEM:

You are given a undirected graph with K(<500) nodes. You need to split graph into two sets such that no two nodes in a set share an edge. If it’s not possible to do so, report that.

EXPLANATION:

We pick up any node and assign it to any arbit set(say A). Naturally, all it’s immediate neighbors should belong to set B and all neighbors of these immediate neighbors will belong to the set A and so on…

So, we’ll do a breadth first search from source node and keep on assigning opposite colors to immediate neighbors. During BFS, for a node u, if we encounter already colored immediate neighbor, we assert that it’s of opposite color, else it is not possible to break nodes into two sets in required way.

Complexity: O(K), using adjacency lists.
O(K*K) using adjacency matrix.

See editorialist’s detailed solution for implementation details.

SOLUTIONS:

Editorialist’s solution

2

Can we use 2 hashtables to segregate the guests into 2 sets? If a guest has no problem(none of the people he hates are in hashtable A) on being placed in hashtable A we place him there, if not we try to seat him on hashtable B. If a guest can’t be placed on either tables we say it is not possible.
This worked correctly for test cases and test cases I created but showed wrong submission.
What could have gone wrong here?

Here’s my code if you want to have a look:
http://www.codechef.com/viewsolution/5643385

Regards,
Ankit

3

@ankitdhall

According to you, if a guest has no problem on being placed in either of the hash tables, you are placing him in table A, though he has an equal opportunity to be placed in hash table B. This may look right on first glance, but on proceeding further you may end up with a condition where you no longer can seat any guest in any hash table. This may be due to the fact that when a guest could sit in any of the hash tables A and B, you are just making him sit in hash table A without giving him a chance to sit in hash table B, which may have led to a solution indeed. This is where your solution might have gone wrong.

4

Please elaborate on your answer with an example. I think I got WA for the same reason.

5

@ksharma377
I think that could be my mistake. But won’t the same case occur while colouring the graph?

6

This is a test case for the case described by @ksharma377. A 6 vertex cycle:

1
6
2 3 4
2 5 6
2 1 5
2 1 6
2 2 3
2 2 4

This case will be correctly handled by BFS as it examines the adjacent nodes of a given node. The hashtable method may start examining a node that is not directly connected to an examined node but the color that should be assigned to it depends on the color of the node already examined. BFS does not color a node that is not directly connected to a node already colored.

7

@bbackspace your 6th line of the test case should contain 2 instead of 4…

1 Like
8

@bbackspace Thanks for the test case, solved my doubts.
Regards, Ankit

9

#include <bits/stdc++.h>

using namespace std;

int casee;

void bfs(vector<vector > v)
{
int n = v.size();
vector set1(n,0);
vector set2(n,0);
bool allvisited = false;
int u = 0;
while(!allvisited) {
set1[u] = 1;
queue q;
q.push(u);
while(!q.empty()) {
int indx = q.front();
q.pop();

        for(int i=0;i<n;i++) {
            if(v[indx][i] && ((set1[indx] && set1[i]) || (set2[indx] && set2[i]))) {
                cout << "Case " << casee << ": " << 0 << " " << 0 << " " << 0 << endl;
                return;
            }
            if(v[indx][i] && (!set1[i] && !set2[i])) {
                if(set1[indx])
                    set2[i] = 1;
                else
                    set1[i] = 1;
                q.push(i);
            }
        }
    }
    int n1=0,n2=0;
    int i=0;
    for(i=0;i<n;i++) {
        if(set1[i])
            n1++;
        if(set2[i])
            n2++;
        if(!set1[i] && !set2[i])
        {
            u = i;
            break;
        }
    }
    if(i == n) {
        cout << "Case " << casee << ": " << 1 << " " << n1 << " " << n2 << endl;
        allvisited = true;
    }
}

}

int main()
{
int n;
cin >> n;
casee = 0;
while(n–) {
casee++;
int k;
int kret;
cin >> k;
kret = k;
vector<vector > v(k,vector(k,0));
for(int i=0;i<k;i++) {
int num;
cin >> num;
while(num–) {
int temp;
cin >> temp;
temp–;
v[i][temp] = 1;
v[temp][i] = 1;
}
}
bfs(v);
}
}

I am getting wrong answer can anybody help??
https://www.codechef.com/viewsolution/7980077
link to code.