思路：裸并查集模板啊。。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstdlib> 5 #include <cstring> 6 #include <map> 7 #include <queue> 8 #include <deque> 9 #include <cmath> 10 #include <vector> 11 #include <ctime> 12 #include <cctype> 13 #include <set> 14 15 using namespace std; 16 17 #define mem0(a) memset(a, 0, sizeof(a)) 18 #define lson l, m, rt << 1 19 #define rson m + 1, r, rt << 1 | 1 20 #define define_m int m = (l + r) >> 1 21 #define Rep(a, b) for(int a = 0; a < b; a++) 22 #define lowbit(x) ((x) & (-(x))) 23 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {} 24 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 25 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 26 27 typedef double db; 28 typedef long long LL; 29 typedef pair<int, int> pii; 30 typedef multiset<int> msi; 31 typedef multiset<int>::iterator msii; 32 typedef set<int> si; 33 typedef set<int>::iterator sii; 34 typedef vector<int> vi; 35 36 const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; 37 const int dy[8] = {0, -1, 0, 1, -1, 1, 1, -1}; 38 const int maxn = 1e5 + 7; 39 const int maxm = 1e5 + 7; 40 const int maxv = 1e7 + 7; 41 const int MD = 1e9 +7; 42 const int INF = 1e9 + 7; 43 const double PI = acos(-1.0); 44 const double eps = 1e-10; 45 46 struct UnionFindSets { 47 vi f; 48 int N; 49 UnionFindSets() { f.clear(); } 50 void clear() { f.clear(); } 51 void resize(int n) { N = n + 2; f.resize(n + 5); } 52 void Init() { for (int i = 1; i <= N; i++) f[i] = i; } 53 int get(int u) { if (u == f[u]) return u; return f[u] = get(f[u]); } 54 void add(int u, int v) { f[get(u)] = get(v); } 55 bool find(int u, int v) { return get(u) == get(v); } 56 }; 57 58 UnionFindSets ufs; 59 60 bool mark[100007]; 61 62 int main() { 63 //freopen("in.txt", "r", stdin); 64 ufs.resize(1e5 + 7); 65 ufs.Init(); 66 int v = 0, a, b, yes = 1; 67 while (1) { 68 scanf("%d%d", &a, &b); 69 if (!v) v = a; 70 mark[a] = mark[b] = 1; 71 if (a == -1 && b == -1) break; 72 if (a == 0 && b == 0) { 73 for (int i = 1; i <= 1e5; i++) { 74 if (mark[i] && ufs.get(i) != ufs.get(v)) { 75 yes = 0; 76 break; 77 } 78 } 79 if (yes) puts("Yes"); 80 else puts("No"); 81 ufs.Init(); 82 mem0(mark); 83 v = 0; 84 yes = 1; 85 continue; 86 } 87 if (ufs.find(a, b)) { 88 yes = 0; 89 } 90 ufs.add(a, b); 91 } 92 return 0; 93 }