This is a disjoint set data structure problem, but with a twist. In this problem, there are around 10000 people and 4 types of operations on them -

setFriends(x, y) shows that x and y are from the same country

setEnemies(x, y) shows that x and y are from different countries

areFriends(x, y) returns true if you are sure that x and y are friends

areEnemies(x, y) returns true if you are sure that x and y are enemies

The first two operations should signal an error if they contradict with your former knowledge. The two relations ‘friends’ (denoted by ~) and ‘enemies’ (denoted by *) have the following properties:

~ is an equivalence relation, i.e.

1. If x ~ y and y ~ z then x ~ z (The friends of my friends are my friends as well.)

2. If x ~ y then y ~ x (Friendship is mutual.)

3. x ~ x (Everyone is a friend of himself.)

* is symmetric and irreflexive

4. If x * y then y * x (Hatred is mutual.)

5. Not x * x (Nobody is an enemy of himself.)

Also

6. If x * y and y * z then x ~ z (A common enemy makes two people friends.)

7. If x ~ y and y * z then x * z (An enemy of a friend is an enemy.)

Operations setFriends(x, y) and setEnemies(x, y) must preserve these properties.

Now, to keep track of the friends, we'll need the usual union find data structure. And to keep track of the enemies, I have used a list from each of the root nodes of different sets. Whenever we join two sets, we need to update the lists properly.

I've designed my solution so that these two properties are always true at any point of execution -

- If two people are friends, they must be on the same set (even if they are not defined as friends, rather they are the common enemies of someone)
- If two people are enemies, that must be indicated on both peoples adjacency list.

I've attached the code that should explain the details of the algorithm. Check the comments -

#include <stdio.h> #include <vector> using namespace std; #define MAXN 10005 #define rep(i,n) for(i=0;i<(n);i++) struct Node { int parent, rank; vector< int > enemyList; } nd[MAXN]; int n; int findSet(int x) { //returns the root of node x if(nd[x].parent == x) return x; return nd[x].parent = findSet(nd[x].parent); } void setFriends(int x, int y) { x = findSet(x); y = findSet(y); if(x == y) return; //already friends int i; rep(i, nd[y].enemyList.size()) if(nd[y].enemyList[i] == x) { //already enemies printf("-1\n"); return; } int j; if(nd[x].rank < nd[y].rank) { //y will be parent of x nd[x].parent = y; //transfer x's enemyList to y's rep(i, nd[x].enemyList.size()) { nd[y].enemyList.push_back(nd[x].enemyList[i]); //update the enemy's list - change x to y as y is the new root rep(j, nd[nd[x].enemyList[i]].enemyList.size()) { if(nd[nd[x].enemyList[i]].enemyList[j] == x) nd[nd[x].enemyList[i]].enemyList[j] = y; } } nd[x].enemyList.clear(); } else if(nd[x].rank > nd[y].rank) { //x will be parent of y nd[y].parent = x; rep(i, nd[y].enemyList.size()) { nd[x].enemyList.push_back(nd[y].enemyList[i]); rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if(nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x; } nd[y].enemyList.clear(); } else { //x & y same rank...so x will be parent of y with x's rank increasing by one nd[y].parent = x; rep(i, nd[y].enemyList.size()) { nd[x].enemyList.push_back(nd[y].enemyList[i]); rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if(nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x; } nd[y].enemyList.clear(); nd[x].rank++; } } void setEnemies(int x, int y) { x = findSet(x); y = findSet(y); if(x == y) { //already friends printf("-1\n"); return; } int i; rep(i, nd[y].enemyList.size()) { if(nd[y].enemyList[i] == x) { //already enemies return; } } int j; //check if x & y both have a common enemy - that will be a contradiction rep(i, nd[x].enemyList.size()) { rep(j, nd[y].enemyList.size()) { if(nd[x].enemyList[i] == nd[y].enemyList[j]) { printf("-1\n"); return ; } } } //set all y's enemies as x's friends rep(i, nd[y].enemyList.size()) { setFriends(x, nd[y].enemyList[i]); } //set all x's enemies as y's friends rep(i, nd[x].enemyList.size()) { setFriends(nd[x].enemyList[i], y); } //do this as x & y's roots may have been changed x = findSet(x); y = findSet(y); nd[x].enemyList.push_back(y); nd[y].enemyList.push_back(x); } int main() { int i; int c,x,y; while(scanf(" %d",&n) == 1) { rep(i,n) nd[i].parent = i, nd[i].rank = 0, nd[i].enemyList.clear(); //make set while(scanf(" %d %d %d",&c, &x, &y) == 3) { if(c == 0) break; if(c == 1) { //set friends setFriends(x,y); } else if(c == 2) { //set enemies setEnemies(x,y); } else if(c == 3) { //are friends x = findSet(x); y = findSet(y); if(x == y) printf("1\n"); else printf("0\n"); } else { //are enemies x = findSet(x); y = findSet(y); rep(i, nd[x].enemyList.size()) if(nd[x].enemyList[i] == y) { printf("1\n"); break; } if(i == nd[x].enemyList.size() ) printf("0\n"); } } //printf("\n"); } return 0; }

This comment has been removed by the author.

ReplyDeleteHere is a much more easier approach:

ReplyDeleteAssociated with each node u, have a complementary node u' which will always be in the opposite set as u.

So the functions become like this:

setFriends(u,v) {

merge(u,v);

merge(u',v');

}

setEnemies(u,v) {

merge(u,v');

merge(u',v);

}

int areEnemies(u,v) {

return findSet(u) == findSet(v');

}

You can define the complementary node u' = OFFSET - u

Nice and easy!

DeleteA similar problem: https://www.spoj.pl/problems/CHAIN

ReplyDelete@Nadeem, Yes, I've noticed it later that the problem can be solved in a much more elegant way. Thanks for your suggestion :)

ReplyDeleteI get a time limit exceeded for this problem.

ReplyDelete