Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
并查集f[y]=x AC,f[x]=y WA,wa的莫名其妙,那个大佬能解释下?#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<stack> #include<vector> #include<map> #include<queue> #define myself i,l,r #define lson i<<1 #define rson i<<1|1 #define Lson i<<1,l,mid #define Rson i<<1|1,mid+1,r #define half (l+r)/2 #define inff 0x3f3f3f3f #define lowbit(x) x&(-x) #define me(a,b) memset(a,b,sizeof(a)) #define min4(a,b,c,d) min(min(a,b),min(c,d)) #define min3(x,y,z) min(min(x,y),min(y,z)) #define max4(a,b,c,d) max(max(a,b),max(c,d)) #define max3(x,y,z) max(max(x,y),max(y,z)) typedef long long ll; const double pi=acos(-1.0); const double E=2.718281828459; using namespace std; const int N=27; char s[1100]; int in[N],out[N]; int f[N],vis[N]; void init() { memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0;i<=N;i++) f[i]=i; } int find(int x) { if(x==f[x]) return f[x]; else return f[x]=find(f[x]); } void unionn(int x,int y) { int fx=find(x); int fy=find(y); if(fx!=fy) f[y]=x; } int main() { int T,t; int x,y; cin>>T; while(T--) { init(); scanf("%d",&t); while(t--) { scanf("%s",s); int len=strlen(s); x=s[0]-'a'; y=s[len-1]-'a'; out[x]++,in[y]++; vis[x]=1,vis[y]=1; unionn(x,y); } int a=0,b=0,cnt=0,falg=0,mark=0; for(int i=0;i<26;i++) { if(vis[i]) { if(f[i]==i) cnt++; if(in[i]!=out[i]) { if(in[i]-out[i]==1) a++; else if(out[i]-in[i]==1) b++; else mark++; } if(cnt>1||mark) { falg=1; break; } } } if(falg||mark) printf("The door cannot be opened.\n"); else { if((a==1&&b==1)||(a==0&&b==0)) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator