/***
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