思路1：
每輸入一個(gè)關(guān)系，合并，最后從1到N，對(duì)于每一個(gè)人，找出它們的祖先，將他們的債debt加到祖先的debt
上。通俗的講，就是每個(gè)集合的成員都將自己的debt加到祖先上，自己歸0，最后看祖先的值是否為0；
最后在從1到N掃一遍如果有debt不為0的，輸出“IMPOSSIBLE”，否則“POSSIBLE”；
缺點(diǎn)：復(fù)雜度高，查詢(xún)復(fù)雜度*N，最后勉強(qiáng)過(guò)了，時(shí)間0.63s
思路2：
路徑壓縮，每輸入一個(gè)關(guān)系，合并。最后從1到N，如果 i 的debt不為0，從 i 到 i 的祖先的路徑不斷壓縮直到
祖先，這樣雖然仍然是N次操作，但由于在壓縮過(guò)程中大部分成員debt歸0，故實(shí)際上進(jìn)行操作的次數(shù)遠(yuǎn)小于N.
最后時(shí)間為0.11,比起上一種方法有了很大提高
Code 1:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int tep,m = n;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[n].father;
a[n].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i){
int tep = find(i);
int tt = a[i].num;
a[i].num -= tt;
a[tep].num += tt;
}
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}
Code 2:
#include <cstdio>
#include <cstring>
struct Node{
int father,v,num;
}a[10002];
int find(int n){
int m = n,tep;
while(n != a[n].father)
n = a[n].father;
while(m != n){
tep = a[m].father;
int tt = a[m].num;
a[m].num -= tt;
a[tep].num += tt;
a[m].father = n;
m = tep;
}
return n;
}
void Union(int root1,int root2){
int t1,t2;
t1 = find(root1),t2 = find(root2);
if(t1 == t2) return ;
else{
if(a[t1].v > a[t2].v){
a[t1].v += a[t2].v;
a[t2].father = t1;
}
else{
a[t2].v += a[t1].v;
a[t1].father = t2;
}
}
}
int main()
{
int n,m,i,j;
bool flag = false;
scanf("%d%d",&n,&m);
for(i = 0;i < n; ++i){
a[i].father = i,a[i].v = 0;
scanf("%d",&a[i].num);
}
while(m--){
scanf("%d%d",&i,&j);
Union(i,j);
}
for(i = 0;i < n; ++i)
if(a[i].num != 0) find(i);
for(i = 0;i < n; i++)
if(a[i].num != 0){
flag = true;
break;
}
if(flag) printf("IMPOSSIBLE\n");
else printf("POSSIBLE\n");
}