Tuesday, February 07, 2012

DisJoint Set Operation

/***
    DisJoint Set Operation
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#include<stdlib.h>

int node,rank[50010],parent[50010],i,sum,edge,a,b,cnt=0,ans[50011],mx,test,temp;

int Find_Set(int x)
{
if(x != parent[x] )
parent[x]=Find_Set(parent[x]);
    return parent[x];
}
void Link(int x,int y)
{
if(rank[x]>rank[y])
{
        parent[y]=x;
        ans[x]+=ans[y];
}
else
{
parent[x]=y;
ans[y] += ans[x];
if(rank[x]==rank[y])
rank[y]=rank[y]+1;
}
}

int main()
{
int set;
    scanf("%d",&test);
while( test-- )
{
set = 0;
   scanf("%d %d",&node,&edge);

for(i=0;i<=50001;i++)parent[i]=i,rank[i]=0,ans[i]=0;
for(i=0;i<node;i++)
{
scanf("%d",&ans[i]);
}
cnt = 0;
for( i=0 ; i<edge ; i++ )
{
   scanf("%d %d",&a,&b);
            a = Find_Set(a);
   b = Find_Set(b);
if( a != b )
{
   Link(a,b);
}
}
for(i=0;i<node;i++)
{
if(parent[i] == i)
{
if(ans[i]!= 0)
{
set = 1;
break;
}

}

}
if(set)printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
return 0;
}
/*
Input:
2
5 3
100
-75
-25
-42
42
0 1
1 2
3 4
4 2
15
20
-10
-25
0 2
1 3
Sample Output
POSSIBLE
IMPOSSIBLE
*/

No comments:

Post a Comment