并查集

/*************************************** *@time 2016/08/14 09:09 *@palce DHU.5005 *description 并查集操作 **************************************/ #include<cstdio> #include<map> using namespace std; /********************************************************************* *@函数名 find_Root *@parameter map<int,int>* Union 储存并查集，如果节点是非根节点则Union[node]表示node的前驱节点， * 如果节点是根节点则Union[node]表示以node为跟节点的树的节点数 *@parameter map<int,bool>* Root 判断节点是否为根节点 *@parameter int x 要找到根节点的点 *@description 根据Union，Root找到一个节点的根节点 **************************************************************************************************************/ int find_Root(map<int,int>* Union,map<int,bool>* Root,int x); /********************************************************************* *@函数名 creat_Tree *@parameter map<int,int>* Union 储存并查集，如果节点是非根节点则Union[node]表示node的前驱节点， * 如果节点是根节点则Union[node]表示以node为跟节点的树的节点数 *@parameter map<int,bool>* Root 判断节点是否为根节点 *@parameter int x ,int y 路径的两端节点 *@description 将节点加入并查集 **************************************************************************************************************/ void creat_Tree(map<int,int>* Union,map<int,bool>* Root,int x,int y); /********************************************************************* *@函数名 count_Trees_Num *@parameter map<int,bool>* Root 判断节点是否为根节点 *@return value int 树的个数，也就是根节点的个数 *@description 统计树的个数，也就是根节点的个数 **************************************************************************************************************/ int count_Trees_Num(map<int,bool>* Root); int find_Root(map<int,int>* Union,map<int,bool>* Root,int x) { while(!(*Root)[x]) x=(*Union)[x]; return x; } void creat_Tree(map<int,int>* Union,map<int,bool>* Root,int x,int y) { int rootX=find_Root(Union,Root,x); int rootY=find_Root(Union,Root,y); //x,y不在同一颗树中，将x所在的树与y所在的是合并 if(rootX!=rootY) { if((*Union)[rootX]>(*Union)[rootY])//x树较大，则将y数加入x数 { (*Union)[rootX]+=(*Union)[rootY];//统计合并后树中节点的个数 (*Union)[rootY]=rootX; (*Root)[rootY]=false; } else { (*Union)[rootY]+=(*Union)[rootX]; (*Union)[rootX]=rootY; (*Root)[rootX]=false; } } } int count_Trees_Num(map<int,bool>* Root) { map<int,bool>::iterator it; int sum=0; for(it=(*Root).begin();it!=(*Root).end();it++) { if(it->second==true) sum++; } return sum; } int main() { int num_Nodes; int num_Routes; map<int,int> Union; map<int,bool> Root; while(scanf("%d",&num_Nodes)&&num_Nodes) { Union.clear(); Root.clear(); for(int i=0;i<num_Nodes;i++) { int node; scanf("%d",&node); Root[node]=true; Union[node]=node; } scanf("%d",&num_Routes); for(int i=0;i<num_Routes;i++) { int start_Node; int end_Node; scanf("%d %d",&start_Node,&end_Node); creat_Tree(&Union,&Root,start_Node,end_Node); } int sum=count_Trees_Num(&Root); printf("sum=%d\n",sum-1); } }

测试样例：

http://acm.hdu.edu.cn/showproblem.php?pid=1232