AcWing 4290. 小希的迷宫
原题链接
简单
作者:
王小强
,
2022-02-25 13:20:12
,
所有人可见
,
阅读 307
并查集找回路
#pragma GCC optimize(2)
#include <iostream>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
using ll = long long int;
const int N = 1E5 + 1E1;
inline ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int p[N];
inline void init(void) { f(i, 0, N) p[i] = i; }
inline int find(int x) {
if (p[x] ^ x) p[x] = find(p[x]);
return p[x];
}
inline void unite(int a, int b) {
p[find(a)] = find(b);
}
inline bool isConnected(int a, int b) {
return find(a) == find(b);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
int u, v;
while ((u = r(), v = r()), u != -1) {
init();
unite(u, v);
bool flag = 1;
while ((u = r(), v = r()), u) {
if (isConnected(u, v)) flag = 0; // 发现回路
if (flag) unite(u, v);
}
puts(flag ? "Yes" : "No");
}
// fclose(stdin);
return ~~(0 ^ 0);
}