UVa 459 Graph Connectivity

题目描述

题目要求计算给定无向图中极大连通子图（即连通分量）的数量。图的节点由大写字母表示，输入给出最大节点名称（即节点集合为A\texttt{A}A到该字符），以及若干条边。需要输出连通分量的个数。

输入格式

第一行一个整数NNN，表示测试用例的数量，后面跟一个空行。每个测试用例的第一行是一个大写字母，表示最大节点名称（例如E表示节点为A,B,C,D,E\texttt{A,B,C,D,E}A,B,C,D,E）。接下来若干行，每行两个大写字母，表示一条边。输入以空行结束。两个连续测试用例之间由一个空行分隔。

输出格式

对于每个测试用例，输出一行一个整数，表示连通分量的个数。两个连续测试用例的输出之间由一个空行分隔。

样例

输入

1 E AB CE DB EC

输出

2

题目分析

本题的核心是计算无向图的连通分量数量。可以使用并查集（Union-Find\texttt{Union-Find}Union-Find）高效求解。

并查集实现

• 初始化：每个节点自成一集合，父节点指向自身。
• 对于每条边(u,v)(u, v)(u,v)，将uuu和vvv所在的集合合并。
• 最终统计有多少个节点是其所在集合的代表元（即parent[i] == i），即为连通分量数。

节点范围

节点从A\texttt{A}A开始到输入的最大字母结束。例如最大字母为E，则节点为A,B,C,D,E\texttt{A,B,C,D,E}A,B,C,D,E共555个。不需要考虑不在该范围内的其他字母。

输入处理

• 第一行是最大节点名称（如E），需要记录该字符并转换为索引。
• 后续行每行两个大写字母表示一条边，可能有多余空格，但每行只包含两个字母。
• 输入以空行结束，需要正确读取。

复杂度分析

并查集操作近似常数，总复杂度O(边数×α(N))O(\text{边数} \times \alpha(N))O(边数×α(N))，其中N≤26N \le 26N≤26。

代码实现

// Graph Connectivity// UVa ID: 459// Verdict: Accepted// Submission Date: 016-07-15// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intparent[26],ranks[26];voidmakeSet(){for(inti=0;i<26;i++){parent[i]=i;ranks[i]=0;}}// 带路径压缩的查找，使用递归实现。intfindSet(intx){return(x==parent[x]?x:parent[x]=findSet(parent[x]));}// 集合的按秩合并。voidunionSet(intx,inty){x=findSet(x);y=findSet(y);if(x==y)return;if(ranks[x]>ranks[y])parent[y]=x;else{parent[x]=y;if(ranks[x]==ranks[y])ranks[y]++;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cin>>cases;cin.ignore(1024,'\n');string line;getline(cin,line);for(inti=1;i<=cases;i++){if(i>1)cout<<endl;makeSet();intmaxIndex=0;while(getline(cin,line),line.length()>0){if(line.length()==1){maxIndex=line.front()-'A';continue;}for(inti=1;i<line.length();i++)unionSet(line[i]-'A',line.front()-'A');}intcounter=0;for(inti=0;i<=maxIndex;i++)if(parent[i]==i)counter++;cout<<counter<<endl;}return0;}