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 |
DPS 判连通性已AC。楼下肯定是你程序的问题。贴上代码: #include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int g[27][27]; int in[27],out[27]; bool vis[27]; int start; int Euler() { int I=0,O=0; for(int i=0; i<26; i++) { if(in[i]==out[i]+1)I++; else if(out[i]==in[i]+1)O++,start=i; else if(in[i]!=out[i])return 0; } if((I==0&&O==0)||(I==1&&O==1))return 1; return 0; } void dfs(int i) { int j; for( j=0; j<26; j++) { if(g[i][j]==0)continue; g[i][j]--; vis[i]=vis[j]=1; dfs(j); } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&m); char str[1001]; memset(g,0,sizeof(g)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=0; i<m; i++) { scanf("%s",str); int u=str[0]-'a'; int v=str[strlen(str)-1]-'a'; g[u][v]++; in[v]++,out[u]++; } for(int i=0;i<26;i++) if(out[i]>0){start=i;break;} bool flag=1; flag=Euler(); if(!flag) { puts("The door cannot be opened."); continue; } memset(vis,0,sizeof(vis)); dfs(start); for(int i=0; i<26; i++) { if(in[i]||out[i]) { if(vis[i]==0) { flag=0; break; } } } if(flag)puts("Ordering is possible."); else puts("The door cannot be opened."); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator