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 |
有限图判欧拉回路—coken#include <iostream> #include <string.h> #include <set> using namespace std; const int MAXN=30; char buf[1005]; set<int> vec; int n; int par[MAXN],indeg[MAXN],outdeg[MAXN]; void prep() { for(int i=0;i<MAXN;i++) { par[i]=i; } } int fnd(int x) { if(par[x]==x) { return x; } return par[x]=fnd(par[x]); } void unite(int x,int y) { int a=fnd(x); int b=fnd(y); par[b]=a; } int main() { int T; cin>>T; while(T--) { vec.clear(); prep(); memset(indeg,0,sizeof(indeg)); memset(outdeg,0,sizeof(outdeg)); cin>>n; for(int i=0;i<n;i++) { cin>>buf; int len=strlen(buf); int u=buf[0]-'a'; int v=buf[len-1]-'a'; unite(u,v); vec.insert(u); vec.insert(v); outdeg[u]++; indeg[v]++; } int root=-1; int s=0; int c1=0,c2=0,c3=0; for(set<int>:: iterator it=vec.begin();it!=vec.end();it++) { int rt=fnd(*it); if(root!=rt) { root=rt; s++; } if(outdeg[*it]-indeg[*it]==1) { c1++; } else if(outdeg[*it]==indeg[*it]) { c2++; } else if(indeg[*it]-outdeg[*it]==1) { c3++; } else ; } if(s==1) { if((c1==1&&c3==1&&c2==vec.size()-2)||(c1==0&&c3==0&&c2==vec.size())) { cout<<"Ordering is possible."<<endl; } else cout<<"The door cannot be opened."<<endl; } else { cout<<"The door cannot be opened."<<endl; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator