1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
| #include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
typedef array<ll, 2> Hash;
static constexpr Hash p = {223333333, 773333333};
static constexpr Hash mod = {1000000033, 1000002233};
Hash operator*(Hash base, const Hash &p) {
for (int i = 0; i < base.size(); i++) base[i] *= p[i];
return base;
}
Hash operator%(Hash base, const Hash &p) {
for (int i = 0; i < base.size(); i++) base[i] %= p[i];
return base;
}
Hash operator+(Hash base, const Hash &p) {
for (int i = 0; i < base.size(); i++) base[i] += p[i];
return base;
}
Hash operator+(Hash base, const ll &p) {
for (int i = 0; i < base.size(); i++) base[i] += p;
return base;
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
vector<int> deg(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
// 该情况下 本身就是个树, 相当于删除0条边形成使得同构, 等价于自己和自己同构
if (m == n - 1) {
cout << "YES" << endl;
return;
}
// 该情况下, 存在多个环, 不存在同构
if (m > n) {
cout << "NO" << endl;
return;
}
// 拓扑排序 删掉所有的树节点,剩下的必然是个环
queue<int> q;
vector<bool> vis(n + 1);
for (int i = 1; i <= n; i++) {
if (deg[i] == 1) {
q.push(i);
}
}
int loopSize = n;
while (!q.empty()) {
int cur = q.front();
q.pop();
vis[cur] = 1;
loopSize--;
for (auto nex: adj[cur]) {
if (!vis[nex] && --deg[nex] == 1) {
q.push(nex);
}
}
}
// 剩下的size就是环的长度
vector<ll> sz(n + 1);
// f(x) = (c + sum(g(x))) % m
function<Hash(int, int)> dfsHash = [&](int cur, int pre) {
Hash res{};
sz[cur] = 1;
vector<Hash> s;
for (auto nex: adj[cur]) {
// 递归遍历子树(由于前面拓扑排序删点, 子树必然是合法的树, 不存在环) 获得所有哈希值
if (vis[nex] && nex != pre) {
auto childHash = dfsHash(nex, cur);
s.push_back(childHash);
sz[cur] += sz[nex];
}
}
// 必须是降序
sort(s.rbegin(), s.rend());
for (auto &si: s) {
for (int i = 0; i < res.size(); i++)
res = (res * p + si) % mod;
}
// 前后顺序不能颠倒 原因未知
res = (res * p + sz[cur]) % mod;
return res;
};
vector<Hash> h;
int pre = 0;
int cur = 0;
// 任意寻找一个没有遍历的点
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cur = i;
break;
}
}
// 由于需要按照环的顺序判断hash, 所以必须是按照以下的方法遍历求hash
for (int i = 0; i < loopSize; i++) {
auto treeHash = dfsHash(cur, -1);
h.push_back(treeHash);
int now = 0;
// 寻找一个没有遍历过的子节点
for (auto nex: adj[cur]) {
if (!vis[nex] && nex != pre) {
now = nex;
break;
}
}
pre = cur;
cur = now;
}
// 如果是奇数环, 那么必须每个相同
// 如果是偶数环, 那么必须隔一个都得相等
// 等价于 h[i] == h[i+2 % mod] nb!
for (int i = 0; i < loopSize; i++) {
if (h[i] != h[(i + 2) % loopSize]) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|