poj1703 种类并查集

本文主要是介绍poj1703 种类并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

种类并查集，比poj1182水

#include <iostream>
#include <cstring>using namespace std;const int N=100005;
int father[N];
int rank[N];
int n,m;void init()
{memset(rank,0,sizeof(rank));for (int i=0;i<=100000;i++)father[i]=i;
}int find(int x)
{if (x==father[x])return x;int t=father[x];father[x]=find(father[x]);rank[x]=(rank[x]+rank[t])%2;return father[x];
}void Union(int a,int b)
{int x=find(a);int y=find(b);if (x==y)return ;father[y]=x;rank[y]=(rank[a]+rank[b]+1)%2;
}int main()
{int T;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);init();char d;int a,b;for (int i=1;i<=m;i++){cin>>d;scanf("%d%d",&a,&b);if (d=='D')Union(a,b);if (d=='A'){ if (find(a)==find(b)){int x=rank[a];int y=rank[b];if (x==y)cout<<"In the same gang."<<endl;elsecout<<"In different gangs."<<endl;}elsecout<<"Not sure yet."<<endl;}}}return 0;
}

这篇关于poj1703 种类并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---