我不知道我为什么脑子抽风一定要用并查集来写这个东西
本地能过样例,但因为cg上c++98不接受unordered_map,试了一下tr1/unordered_map,铩羽而归
但写都写了,在这里存个档权当留念 : (
8-1:无向图的连通分量
【问题描述】求解无向图的连通分量。
【输入形式】第一行:顶点数 边数;第二行:顶点;第三行及后面:边(每一行一条边)
【输出形式】分量:顶点集合(顶点按从小到大排序输出)(每个连通分量输出占用一行)
【样例输入】
6 5
ABCDEF
A B
A E
B E
A F
B F
【样例输出】
1:ABEF
2:C
3:D
【代码】
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int n, e; //节点数和边数
char x, y; //边的两个节点
string v; //节点集合
unordered_map<char, int> p; //父节点数组
unordered_map<char, vector<char>> m; //集合节点数组
//递归查找根节点(路径压缩)
int find(char x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> e >> v;
//初始化并查集,每个节点自身为一集合
for (int i = 0; i < n; i++) p[v[i]] = v[i];
//合并节点
while (e--) {
cin >> x >> y;
p[find(x)] = find(y);
}
//将属于相同集合的节点归类
for (auto& i : p) {
char root = find(i.first); //找到节点所在集合的根节点
m[root].push_back(i.first); //将节点添加到对应的集合中
}
int id = 1;
for (auto& i : m) {
cout << id++ << ":";
//获取当前集合的节点列表
vector<char> node = i.second;
for (char c : node) cout << c;
cout << endl;
}
return 0;
}