图论三元环（并查集的高级应用）

题目描述

无聊的你回想起了A题的三角形，于是你想到了一个新的问题：

在一个连通图中，任何一条边都属于一个集合

如果两条边 a,b属于同一个集合当且仅当满足以下条件之一

1.  a,b 是某一个三角形的两条边

2. 存在边 c ，使得 a,c 属于同一个集合且 b,c 属于同一个集合

那么请问，以下连通图的所有边是否都属于同一个集合？

输入描述:

第一行输入 T,表示 T 组样例

每组样例第一行输入两个正整数 n,m

接下来 m 行，第i行输入两个正整数 ai,bi​,表示第i条边连接 ai,bi​结点

数据保证图联通，且没有重边和自环

输出描述:

输出一个字符串表示答案

是输出 "Yes"

否输出 "No"

示例1

输入

1
3 3
1 2
1 3
3 2

输出

Yes

示例2

输入

1
4 5
1 2
1 4
2 3
2 4
3 4

输出

Yes

示例3

输入

1
3 2
1 2
1 3

输出

No

示例4

输入

1
4 4
1 2
1 4
2 3
3 4

输出

No

先放在这里

代码：

#include <bits/stdc++.h>
using namespace std; // 引入 std 命名空间using i64 = long long;
using u64 = unsigned long long;void solve() {int n, m;cin >> n >> m;vector<int> p(m + 1);auto find = [&] (auto self, int &x) -> int {if (x == p[x]) return x;return p[x] = self(self, p[x]);};auto merge = [&] (int &a, int &b) -> void {int fa = find(find, a), fb = find(find, b);if (fa != fb) {p[fb] = fa;}};vector<int> in(n + 1), u(m + 1), v(m + 1);for (int i = 1; i <= m; i++) {cin >> u[i] >> v[i];in[u[i]]++;in[v[i]]++;p[i] = i;}vector<vector<pair<int, int>>> e(n + 1);for (int i = 1; i <= m; i++) {if (in[u[i]] < in[v[i]] || (in[u[i]] == in[v[i]] && u[i] < v[i])) {e[v[i]].push_back({u[i], i});} else {e[u[i]].push_back({v[i], i});}}vector<pair<int, int>> vis(n + 1);for (int i = 1; i <= n; i++) {for (auto [x, j] : e[i]) vis[x] = {i, j};for (auto [x, j] : e[i]) {for (auto [y, k] : e[x]) {if (vis[y].first == i) {merge(k, j);merge(j, vis[y].second);}}} }int ans = 0;for (int i = 1; i <= m; i++) {if (p[i] == i) ans++;}if (ans == 1) cout << "Yes\n";else cout << "No\n";
}int main() {ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);i64 t = 1; cin >> t;while (t--) {solve();}
}