洛谷多校第2轮.E——Anan and Minecraft【并查集】（判断图同构）

题目传送门

题意

• 初始给了你两个点数一样的空图，你在每个时刻会有一些连边操作（无向），在每个时刻，判断两个图任意两点的连通性是否相同

题解

• 可以并查集判断图是否连通同构
• 两种方法：
  1. 类似哈希，每个点随机值，合并两个区域时异或，两个图所有区域的和相等就认为是连通同构
  2. 每个图一个队列，一个图有加边操作时，另一个图队列加入这条边，每次操作后判断每个队列内的边是否已经连通，若连通则pop，如果两个队列都是空的，则认为连通同构
• $复杂度O(mK)$

AC-Code

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 7;vector<int> G[2][maxn];
struct Edge {
    int u, v;Edge(int a, int b) : u(a), v(b) {
    }
};void init(int n, int m) {
    for (int i = 0; i <= n; ++i) {
    G[0][i].clear();G[1][i].clear();}
}
struct UFS {
    
#define N maxnint f[N];unsigned int rank[N];UFS() {
    }void init() {
    for (int i = 0; i < N; ++i) {
    f[i] = i;	rank[i] = 0;}}int getF(int x) {
    return f[x] == x ? x : (f[x] = getF(f[x]));}void merge(int x, int y) {
    x = getF(x), y = getF(y);if (x == y)	return;if (rank[x] < rank[y])	f[x] = y;else	f[y] = x;if (rank[x] == rank[y])	++rank[x]; // 走else合并}bool isUnion(int x, int y) {
    return getF(x) == getF(y);}
};
int main() {
    int n, m;	while (cin >> n >> m) {
    init(n, m);queue<Edge> q[2];UFS ufs[2];		ufs[0].init();		ufs[1].init();for (int i = 1; i <= m; ++i) {
    int id, u, v;	cin >> id >> u >> v;G[id - 1][u].push_back(v);G[id - 1][v].push_back(u);q[id - 1].push(Edge(u, v));ufs[id - 1].merge(u, v);while (!q[0].empty()) {
    auto e = q[0].front();if (ufs[1].isUnion(e.u, e.v))	q[0].pop();else	break;}while (!q[1].empty()) {
    auto e = q[1].front();if (ufs[0].isUnion(e.u, e.v))	q[1].pop();else	break;}cout << ((q[0].empty() && q[1].empty()) ? "A" : "B") << endl;}}return 0;
}