并查集习题题解（洛谷题单）

本篇对应源码见仓库 solutions/xcpc/algorithm/graph/dsu/。

修复公路

题意

给出村庄数 N，和公路数 M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

思路

普通并查集的模板题，加上size 判断最大集合大小是否为 n

示例代码

struct DSU {
	int n;
	vector<int> fa, rank;
	vector<int> sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		rank.resize(n + 1);
		sz.resize(n + 1, 1);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int size(int x) {
		return sz[find(x)];
	}

	bool ok() {
		return *max_element(all(sz)) == n;
	}
};

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;
    DSU uf(n);

    vector<array<int, 3>> arr(m);
    fer(i, 0, m) cin >> arr[i][1] >> arr[i][2] >> arr[i][0];

    sort(all(arr));

    for(auto &[t, a, b] : arr) {
    	uf.merge(a, b);
    	if(uf.ok()) {
    		cout << t << '\n';
    		return 0;
    	}
    }
    cout << -1 << '\n';
    return 0;
}

一中校运会之百米跑

题意

有 N 个选手的名字。和 $M（1≤M≤106）$ 句话，即告诉你学生 A 与学生 B 在同一个组里。会问你 $K（1≤K≤106）$ 句话，即学生 X 和学生 Y 是否在同一组里。若是则输出 Yes.，否则输出 No.。

思路

是一个变式，变式在于每个节点不是数字，而是字符串。有两种处理方法：

使用 map 进行映射
- map<string, string> fa 来表示一个节点的根
- 所以对 int 型节点的操作都变为 string
- 见示例代码1
给每个 string 分配一个 id 编号，从而继续使用 DSU 模板
- 用 map<string, int> 判断每个 string 是否分配编号，和存储 string 和 id 的映射
- 如果需要反向根据 id 查找 string 的话可以用另外用一个 map<int, string> 来存储反响映射关系
- 见示例代码2

示例代码1

struct DSU {
	int n;
	map<string, string> fa;
	map<string, int> sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {

	}

	string find(string x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}
	void merge(string x, string y) {
		string rx = find(x), ry = find(y);
		if(rx != ry) {
			if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(string x, string y) {
		return find(x) == find(y);
	}

	int size(string x) {
		return sz[find(x)];
	}
};

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;
    DSU uf(n);

    fer(i, 0, n) {
    	string name;
    	cin >> name;
    	uf.fa[name] = name;
    }

    while(m--) {
    	string a, b;
    	cin >> a >> b;
    	uf.merge(a, b);
    }

    int k;
    cin >> k;
    while(k--) {
    	string a, b;
    	cin >> a >> b;
    	cout << (uf.same(a, b) ? "Yes." : "No.") << '\n';
    }

    return 0;
}

示例代码2

struct DSU {
	int n;
	vector<int> fa, rank;
	vector<int> sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		rank.resize(n + 1);
		sz.resize(n + 1, 1);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int size(int x) {
		return sz[find(x)];
	}
};

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;

    DSU uf(n);
    int cnt = 0;
    map<string, int> mp;

    fer(i, 0, n) {
    	string name;
    	cin >> name;
    	if(!mp[name]) {
    		mp[name] = ++cnt;
    	}
    }

    while(m--) {
    	string a, b;
    	cin >> a >> b;
    	int id1 = mp[a], id2 = mp[b];
    	uf.merge(id1, id2);
    }

    int k;
    cin >> k;
    while(k--) {
    	string a, b;
    	cin >> a >> b;
    	int id1 = mp[a], id2 = mp[b];
    	cout << (uf.same(id1, id2) ? "Yes." : "No.") << '\n';
    }

    return 0;
}

[BalticOI 2003] 团伙

题意

现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道：

一个人的朋友的朋友是朋友
一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入：

如果 opt 为 F，则表明 p 和 q 是朋友。
如果 opt 为 E，则表明 p 和 q 是敌人。

思路

思路1：

如果是朋友，则直接两人合并，如果是敌人，则先相互存储到各自的敌人集合中，然后离线处理（合并）每个人的敌人（敌人的敌人是朋友）
这种方法可以 AC ，但是效率比较低

思路2：

扩展域并查集
每个人 i 有两个属性，一个是朋友 i ，一个是敌人 i + n
如果是朋友则合并两人，注意一定不能将两人的敌人进行合并，因为题目没有说朋友的敌人是敌人，也没说敌人的朋友是敌人
如果是敌人则相互合并到第二个属性中

示例代码1

class DSU {
private:
	int n;
	vector<int> parent, rank;

public:
	vector<int> sz;
	// 节点编号从 0 开始
	DSU(int n) : n(n) {
		parent.resize(n);
		iota(all(parent), 0);
		rank.resize(n);
		sz.resize(n, 1);
	}

	int find(int x) {
		if(x != parent[x]) {
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			parent[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;
    set<int> st[n];
    DSU uf(n);

    while(m--) {
    	char op;
    	int a, b;
    	cin >> op >> a >> b;
    	a--, b--;
    	if(op == 'F') uf.merge(a, b);
    	else {
    		st[a].insert(b);
    		st[b].insert(a);
    	}
    }
    fer(i, 0, n) {
    	int x = *st[i].begin();
    	for(auto a : st[i]) uf.merge(x, a);
    }
	set<int> res;
	fer(i, 0, n) {
		res.insert(uf.find(i));
	}
	cout << res.size() << '\n';

    return 0;
}

示例代码2

struct DSU {
	int n;
	vector<int> fa, sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		sz.resize(n + 1, 1);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			//if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int size(int x) {
		return sz[find(x)];
	}
};

signed main() {
    IOS;

    int n;
    cin >> n;
    DSU uf(2 * n);

    int m;
    cin >> m;
    while(m--) {
    	char op;
    	int a, b;
    	cin >> op >> a >> b;
    	if(op == 'F') {
    		uf.merge(a, b);
    		//uf.merge(a + n, b + n);
    	} else {
    		uf.merge(b, a + n);
    		uf.merge(a, b + n);
    	}
    }

    int ans = 0;
    fer(i, 1, n + 1) {
    	if(uf.find(i) == i) ans++;
    }
    cout << ans << '\n';

    return 0;
}

[JSOI2008] 星球大战

题意

给出 $n$ 个星球和连通关系，现在会依次打击掉一些星球，求每次打击后有几个连通块

思路

肯定不能在线处理，对每次查询都统计有多少个连通块。这题可以逆向处理，先将所有题目操作的星球打掉，然后逆序添加星球，统计连通块数，然后逆序输出答案。

示例代码

struct DSU {
	int n;
	vector<int> fa, sz;

	// 节点编号从 1 开始
	DSU(int n) : n(n) {
		fa.resize(n + 1);
		iota(all(fa), 0);
		sz.resize(n + 1, 1);
	}

	int find(int x) {
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}

	void merge(int x, int y) {
		int rx = find(x), ry = find(y);
		if(rx != ry) {
			if(sz[rx] < sz[ry]) swap(rx, ry);
			fa[ry] = rx;
			sz[rx] += sz[ry];
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int size(int x) {
		return sz[find(x)];
	}
};

signed main() {
    IOS;

    int n, m;
    cin >> n >> m;
    DSU uf(n);

    vector<vector<int>> g(n + 1);

    fer(i, 0, m) {
    	int a, b;
    	cin >> a >> b;
    	a++, b++;
    	g[a].push_back(b), g[b].push_back(a);
    }
    int k;
    cin >> k;
    vector<bool> st(n + 1, true);
    vector<int> arr(k);
    fer(i, 0, k) {
    	cin >> arr[i];
    	arr[i]++;
    	st[arr[i]] = false;
    }

    int cnt = n - arr.size();
    fer(u, 1, n + 1) {
    	if(!st[u]) continue;

    	for(auto v : g[u]) {
    		if(st[v]) {
    			if(!uf.same(u, v)) cnt--;
    			uf.merge(u, v);
    		}
    	}
    }

    vector<int> res;
    ferd(i, k - 1, 0) {
    	res.push_back(cnt);

    	int u = arr[i];
    	st[u] = true;

    	bool ok = false;
    	fer(j, 0, g[u].size()) {
    		int v = g[u][j];
    		if(st[v]) {
    			if(j == 0) {
    				ok = true;
    				uf.merge(u, v);
    			} else {
    				if(!uf.same(u, v)) cnt--;
    				uf.merge(u, v);
    			}
    		}
    	}
    	if(!ok) cnt++;
    }
    reverse(all(res));
    cout << cnt << '\n';
    for(auto x : res) cout << x << '\n';

    return 0;
}

修复公路

题意

思路

示例代码

一中校运会之百米跑

题意

思路

示例代码1

示例代码2

[BalticOI 2003] 团伙

题意

思路

示例代码1

示例代码2

[JSOI2008] 星球大战

题意

思路

示例代码

推荐文章

相关文章

搜索文章