首页 > 代码库 > 并查集（与应用举例）
并查集（与应用举例）
并查集：管理元素分组情况的数据结构。
主要操作：1. 查询元素 A 和 B 是否同一组。 2. 合并元素 A 和 元素 B 所在的组。
#include <iostream>using namespace std;const int N = 100;int Parent[N], Rank[N];void init(int n) { for (int i = 0; i < n; ++i) { Parent[i] = i; Rank[i] = 1; }}int find(int x) { if(Parent[x] == x) return x; else return Parent[x] = find(Parent[x]);}void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; if(Rank[x] < Rank[y]) { Parent[x] = y; } else { Parent[y] = x; if(Rank[x] == Rank[y]) Rank[x]++; }}bool same(int x, int y) { return find(x) == find(y);}int main () { init(10); unite(1, 2); unite(2, 3); unite(3, 4); unite(4, 5); unite(5, 6); cout << Rank[find(6)] << endl << same(1, 6) << endl; return 0;}
应用举例： N（0 <= N <= 10000） 个人的编号依次为 0 ~ N-1，现在对这 N 个人的成绩排名，可用的关于排名的信息有 M（0 <= M <= 20000） 条，这些信息可能有三种情况，分别是"A > B","A = B","A < B", 分别表示A的Rating高于B, 等于B, 小于B。 要求： 根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。
注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。
Link: (http://acm.hdu.edu.cn/showproblem.php?pid=1811)
思路：首先，并查集将相等的归类，每类中只拿出根节点来比就好。
其次，构建有向图（每条边从Rating 高的指向 Rating 低的），此处用邻接表表示（此时注意查 冲突【若是同类中两个人却表现不同大小，则 冲突】）。
最后，拓扑排序。若是没有一个序列（有环）则 冲突；若是有多个序列（同时出现多个点入度为 0），则 信息不全； 若只有一个序列，则 OK。
#include <iostream>#include <vector>#include <queue>using namespace std;const int MAX_N = 10000;int par[MAX_N], indegree[MAX_N]; // For Union-Find Sets/* Adjacent list For Topological sort */vector<vector<int> > Pos(MAX_N, vector<int>());/************************************************************************//* 并查集的基本操作 *//************************************************************************/void init(int n) { for (int i = 0; i < n; ++i) { par[i] = i; indegree[i] = 0; }}int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); }}void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; par[y] = x;}bool same(int x, int y) { return find(x) == find(y);}/********************************************************************************/void insert (int x, int y) { Pos[x].push_back(y);}int main () { int N, M; cin >> N >> M; init(N); int cnt = N; vector<int> L(M), R(M); vector<char> Signs(M); for (int i = 0; i < M; ++i) { cin >> L[i] >> Signs[i] >> R[i]; if (Signs[i] == ‘=‘) { unite(L[i], R[i]); --cnt; } } bool conflict = false; for (int i = 0; i < M; ++i) { if (Signs[i] == ‘=‘) continue; if (find(L[i]) == find(R[i])) { cout << "CONFLICT" << endl; conflict = true; break; } else if (Signs[i] == ‘>‘) { insert(find(L[i]), find(R[i])); ++indegree[find(R[i])]; } else { insert(find(R[i]), find(L[i])); ++indegree[find(L[i])]; } } if (conflict) return 0; queue<int> qu; for (int i = 0; i < N; ++i) { if (indegree[i] == 0 && i == find(i)) { qu.push(i); --cnt; } } bool uncertain = false; while(!qu.empty()) { if(qu.size() > 1) { uncertain = true; break; } int cur = qu.front(); for (size_t i = 0; i < Pos[cur].size(); ++i) { if(--indegree[Pos[cur][i]] == 0) { qu.push(Pos[cur][i]); --cnt; } } qu.pop(); } if (cnt > 0) { cout << "CONFLICT" << endl; return 0; } else if (uncertain) { cout << "UNCERTAIN " << endl; return 0; } else { cout << "OK" << endl; } return 0;}
并查集（与应用举例）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。