UVA 10441 Catenyms 欧拉道路-白红宇

UVA 10441 Catenyms 欧拉道路

阅读量：6956 次

发布时间：2019-06-27

本文共 2027 字，大约阅读时间需要 6 分钟。

// #pragma comment(linker, "/STACK:1024000000,1024000000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    using namespace std;typedef long long ll;typedef pair
                    
                      pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,rvoid debug(){#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}char getch(){ char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}struct point{ int x,y,dir,col, t; point() {} point (int a,int b,int c,int d,int e) { x=a; y=b; dir=c; col=d; t=e; }};int vis[1001];string dic[1001];stack
                     
                       sta;int n;int f(int u){ for(int i=1;i<=n;i++)if(!vis[i]&&dic[i][0]==u+'a') { vis[i]=1; f(dic[i][dic[i].size()-1]-'a'); sta.push(i); } return 0;}int da[26];int cvis[26];int find(int a){ return a==da[a]?a:da[a]=find(da[a]);}int can(){ for(int i=0;i<26;i++)da[i]=i; memset(cvis,0,sizeof(cvis)); for(int i=1;i<=n;i++) { int fa=find(dic[i][0]-'a'); int fb=find(dic[i][dic[i].size()-1]-'a'); cvis[dic[i][0]-'a']=1;cvis[dic[i][dic[i].size()-1]-'a']=1; if(fa!=fb)da[fa]=fb; } int num=0; for(int i=0;i<26;i++) if(da[i]==i&&cvis[i]==1)num++; return num==1?1:0;}int main(){ int t; cin>>t; for(int ca=1;ca<=t;ca++) { cin>>n; int deg[26]={ 0}; for(int i=1;i<=n;i++) { cin>>dic[i]; } sort(dic+1,dic+1+n); for(int i=1;i<=n;i++) { deg[dic[i][0]-'a']++;deg[dic[i][dic[i].size()-1]-'a']--; } int in=-1,out=-1; int allzero=1; for(int i=0;i<26;i++) { if(deg[i]==1) { allzero=0; if(in!=-1) { in=-1;break; } else in=i; }else if(deg[i]==-1) { allzero=0; if(out!=-1) { out=-1;break; } else out=i; }else if(deg[i]!=0) { allzero=0; in=-1;out=-1;break; } } if(allzero) { in=dic[1][0]-'a';out=dic[1][0]-'a'; } if(in==-1||out==-1||!can()) { cout<<"***"<