You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
55 lines
1.2 KiB
55 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int N = 100010;
|
|
|
|
bool st[N];
|
|
bool flag;
|
|
int edges, points;
|
|
//最简并查集
|
|
int p[N];
|
|
int find(int x) {
|
|
if (p[x] != x) p[x] = find(p[x]); //路径压缩
|
|
return p[x];
|
|
}
|
|
//合并集合
|
|
bool join(int a, int b) {
|
|
if (find(a) == find(b)) return false;
|
|
p[find(a)] = find(b);
|
|
return true;
|
|
}
|
|
|
|
//初始化并查集
|
|
void init() {
|
|
for (int i = 0; i < N; i++) p[i] = i;
|
|
//初始化状态数组
|
|
memset(st, false, sizeof(st));
|
|
flag = true;
|
|
edges = points = 0;
|
|
}
|
|
|
|
int main() {
|
|
int a, b;
|
|
//初始化
|
|
init();
|
|
while (~scanf("%d%d", &a, &b), ~a && ~b) {
|
|
if (a && b) {
|
|
edges++; //增加一条边
|
|
if (!st[a]) {
|
|
st[a] = true;
|
|
points++;
|
|
}
|
|
if (!st[b]) {
|
|
st[b] = true;
|
|
points++;
|
|
}
|
|
if (!join(a, b)) flag = false;
|
|
} else {
|
|
//这个是应付AcWing的黑心数据 0 0 -1 -1而加的特判
|
|
//如果连通，并且，无环
|
|
flag && (edges == points - 1 || edges == 0) ? puts("Yes") : puts("No");
|
|
init();
|
|
}
|
|
}
|
|
return 0;
|
|
} |