[NOI2015]程序自动分析

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<map>
 7 #include<cctype>    //isdigit 
 8 using namespace std;
 9 typedef long long ll;
10 #define enter printf("\n")
11 const int INF = 0x3f3f3f3f;
12 const int maxn = 1e5 + 5;
13 inline ll read()
14 {
15     ll ans = 0;
16     char ch = getchar(), last = ‘ ‘;
17     while(!isdigit(ch)) {last = ch; ch = getchar();}
18     while(isdigit(ch))
19     {
20         ans = ans * 10 + ch - ‘0‘; ch = getchar();    
21     }
22     if(last == ‘-‘) ans = -ans;
23     return ans;
24 }
25 
26 int t;
27 struct Node
28 {
29     ll x, y;
30 }a[maxn];
31 int pos = 0, cnt = 0;
32 
33 map<ll, int> mp;
34 
35 int p[maxn << 1];
36 void init(const int& n)
37 {
38     pos = 0; cnt = 0;
39     mp.clear(); 
40     memset(p, 0, sizeof(p));
41     for(int i = 1; i <= (n << 1); ++i) p[i] = i;
42 }
43 int Find(const int& x)
44 {
45     return p[x] == x ? x : p[x] = Find(p[x]);
46 }
47 void merge(const int& x, const int& y)
48 {
49     int px = Find(x), py = Find(y);
50     if(px == py) return;
51     p[px] = py; return;
52 }
53 
54 int main()
55 {
56     t = read();
57     while(t--)
58     {
59 
60         int n = read();
61         init(n);
62         for(int i = 1; i <= n; ++i)
63         {
64             ll x = read(), y = read();
65             int e = read();
66             int tpa = mp[x], tpb = mp[y];
67             if(!tpa) {mp[x] = ++cnt; tpa = cnt;}
68             if(!tpb) {mp[y] = ++cnt; tpb = cnt;}
69             if(e) merge(tpa, tpb);        
70             else {a[++pos].x = x; a[pos].y = y;}
71         }
72         bool flag = true;
73         for(int i = 1; i <= pos; ++i)
74         {
75             int tpa = mp[a[i].x], tpb = mp[a[i].y];
76             if(a[i].x == a[i].y) {flag = false; break;}
77             if(Find(tpa) == Find(tpb)) {flag = false; break;}
78         }
79         printf("%s\n", flag ? "YES" : "NO");
80     }
81     return 0;
82 }