tyvj 1017 中如何识别冗余关系？

本文共计324个文字，预计阅读时间需要2分钟。

题目链接：冗余关系判断内容：非常复杂的一道题目，需要查集裸题，给你n个关系，判断有几个关系是不必要的（我们可以从前面的关系中推出）。只需要判断当前两个值是否在一个集合中。

题目链接：​​冗余关系​​

很蠢的一道题目嘛，并查集裸题，给你n个关系，判断有几个关系是不需要的（我们可以从之前的关系中推出来），只需要判断当前两个值是不是在一个集合里面就可以了，在就证明多余，其他看代码

#include <bits/stdc++.h>

using namespace std;

int father[1005];

int Find(int x){
if(x == father[x]) return x;
return father[x] = Find(father[x]);
}

bool UnionSet(int x,int y){
int p = Find(x);
int q = Find(y);
if(q != p) {father[p] = q;return false;}
return true;
}

int main(){
int n,m,cot = 0,a,b;
while(cin>>n>>m){
cot = 0;
for(int i = 0;i <= m;i++)
father[i] = i;
while(n--){
cin>>a>>b;
if(UnionSet(a,b)) cot++;
}
cout<<cot<<endl;
}
return 0;
}