$n \leq 1000000$個相等或不等關系描述一些變量,問能否成立,多組資料。
走錯片場?普及題誤入noi
1 //#include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 //#include<math.h>
5 //#include<set>
6 //#include<queue>
7 //#include<bitset>
8 //#include<vector>
9 #include<algorithm>
10 #include<stdlib.h>
11 using namespace std;
12
13 #define LL long long
14 int qread()
15 {
16 char c; int s=0,f=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (f=-1);
17 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*f;
18 }
19
20 //Pay attention to '-' , LL and double of qread!!!!
21
22 int T,n;
23 #define maxn 2000011
24 int ufs[maxn];
25 int find(int x) {return x==ufs[x]?x:(ufs[x]=find(ufs[x]));}
26 void Union(int x,int y) {x=find(x); y=find(y); if (x!=y) ufs[x]=y;}
27
28 #define maxh 1000007
29 struct Hash
30 {
31 struct Edge{int v,id,next;}edge[maxh]; int first[maxh],le;
32 void clear() {memset(first,0,sizeof(first)); le=1;}
33 int insert(int x)
34 {
35 int h=x%maxh;
36 for (int i=first[h];i;i=edge[i].next) if (edge[i].v==x) return edge[i].id;
37 Edge &e=edge[le]; e.v=x; e.id=le; e.next=first[h]; first[h]=le++;
38 return le-1;
39 }
40 }h;
41
42 struct Node{int x,y;}eee[maxn]; int le=0;
43 int main()
44 {
45 T=qread();
46 while (T--)
47 {
48 n=qread();
49 int op,x,y; h.clear(); le=0;
50 for (int i=1;i<=n+n;i++) ufs[i]=i;
51 for (int i=1;i<=n;i++)
52 {
53 x=qread(); y=qread(); op=qread();
54 x=h.insert(x); y=h.insert(y);
55 if (!op) eee[++le]=(Node){x,y};
56 else Union(x,y);
57 }
58 bool flag=1;
59 for (int i=1;i<=le;i++) if (find(eee[i].x)==find(eee[i].y)) flag=0;
60 if (flag) puts("YES"); else puts("NO");
61 }
62 return 0;
63 }
View Code
轉載于:https://www.cnblogs.com/Blue233333/p/9283692.html