tyvj1017 - 冗余关系 ——并查集

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1017 并查集

#include <cstdio>
#include <cstdlib>
using namespace std;
int parent[1001],n,m;
void init() {for(int i=1;i<=m;++i)parent[i]=-1; }
int Find(int x) {int s; for(s=x;parent[s]>=0;s=parent[s]);while (s!=x) {int tmp=parent[x];parent[x]=s;x=tmp; }return s; }
void Union(int R1,int R2)
{
    int r1=Find(R1),r2=Find(R2),tmp=parent[r1]+parent[r2]; if (parent[r1]<parent[r2]) parent[r2]=r1,parent[r1]=tmp;
    else parent[r1]=r2,parent[r2]=tmp;
}
int main(void)
{
    freopen("in1.txt","r",stdin);
    int cnt=0;scanf("%d%d",&n,&m); init();
    while (n--) {
        int a,b; scanf("%d%d",&a,&b); if(Find(a)==Find(b)) cnt++;
        else Union(a,b);
    } printf("%d\n",cnt);
    return 0;
}

=_=