2 条题解
-
0DRAINF LV 8 MOD @ 2021-01-28 11:33:10
#include<bits/stdc++.h> #define MAXN 100005 using namespace std; int n,fa[MAXN],u[MAXN],v[MAXN],t[MAXN]; int getfa(int Node){ if(Node==fa[Node])return Node; else return fa[Node]=getfa(fa[Node]); } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;++i){ fa[i]=i; } for(int i=1;i<=n;++i){ cin>>u[i]>>v[i]>>t[i]; if(t[i]==1){ int fau,fav; fau=getfa(u[i]); fav=getfa(v[i]); if(fav!=fau){ fa[fav]=fau; } } } int fl=1; for(int i=1;i<=n;++i){ int fav,fau; fav=getfa(v[i]); fau=getfa(u[i]); if(t[i]==0&&fav==fau)fl=0; if(t[i]==1&&fav!=fau)fl=0; } if(fl)puts("Yes"); else puts("No"); return 0; }
-
02021-01-27 22:09:28@
#include<cstdio> #include<cstring> #include<algorithm> #include<stdio.h> using namespace std; const int N=200005; pair<int,int>unequal[N]; int t,num,sum,x[N],y[N],tof[N],father[N],d[N]; int find(int x) { if(father[x]==x) { return x; } else { return father[x]=find(father[x]); } } void getunion(int x,int y) { x=find(x),y=find(y); if(x!=y) { father[x]=y; } } void dig(int sum) { sort(d+1,d+sum+1); int m=unique(d+1,d+sum+1)-d-1; for(int i=1;i<=t;++i) { x[i]=lower_bound(d+1,d+m+1,x[i])-d; y[i]=lower_bound(d+1,d+m+1,y[i])-d; } } int main() { int i,t,a,b; scanf("%d",&t); num=0,sum=0; for(i=1;i<=t;i++) { father[i]=i; } for(i=1;i<=t;++i) { scanf("%d%d%d",&x[i],&y[i],&tof[i]); d[++sum]=x[i]; d[++sum]=y[i]; } dig(sum); for(i=1;i<=t;++i) { if(tof[i]==1) { getunion(x[i],y[i]); } else { unequal[++num]=make_pair(x[i],y[i]); } } for(i=1;i<=num;++i) { a=find(unequal[i].first); b=find(unequal[i].second); if(a==b){ printf("No"); goto end; } } printf("Yes"); end:; }
- 1