并查集 带压缩路径的版本

#include <iostream>``using namespace std;``typedef struct``{``int a,b;``}road;``const int MAX=5001;``int N,M,K;``int father[MAX];``int rank[MAX];``road rd[500000];``void make_set()``{``int i;``for``(i=1;i<=N;i++)``{``father[i]=i;``rank[i]=0;``}``}``int find_set(``int x)``{``if``(x!=father[x])``father[x]=find_set(father[x]);``return father[x];``}``void union_set(``int x,``int y)``{``x=find_set(x);``y=find_set(y);``if``(x==y)``return ;``if``(rank[x]>rank[y])``father[y]=x;``else``{``father[x]=y;``if``(rank[x]==rank[y])``rank[y]++;``}``}``int main()``{``cin>>N>>M>>K;``int i,j;``int start,end;``int input;``for``(i=1;i<=M;i++)``{``cin>>start>>end;``rd[i].a=start;``rd[i].b=end;``}``for``(i=1;i<=K;i++)``{``int cnt=-2;``cin>>input;``make_set();``for``(j=1;j<=M;j++)``{``if``(rd[j].a!=input && rd[j].b!=input)``union_set(rd[j].a,rd[j].b);``}``for``(j=1;j<=N;j++)``{``if``(father[j]==j)``cnt++;``}``cout<<cnt<<endl;``}``return 0;``}``/**************************************************************``Problem: 1325``User: feng345feng``Language: C++``Result: Accepted``Time:800 ms``Memory:5456 kb``****************************************************************/原文链接: https://www.cnblogs.com/Knuth/archive/2011/09/26/2191799.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍