HDUPlay on Words

本文主要是介绍HDUPlay on Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.定理：无向图G有欧拉通路的充分必要条件是G为连通图，并且G仅有两个奇度结点或者无奇度结点。
（1）当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
（2）当G是无奇度结点的连通图时，G必有欧拉回路。

2.一个有向图D具有欧拉通路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大１，另一个顶点的入度比出度小１． 推论：一个有向图D是欧拉图（具有欧拉回路），当且仅当D是连通的，且所有顶点的出度等于入度。

文字摘自  点击打开链接

const  int  maxn = 30 ;
int    father[maxn]  ;int  getf(int x){if(x == father[x]) return x ;else  return father[x] = getf(father[x]) ;
}void  _merge(int u , int v){u = getf(u) ;v = getf(v) ;if(u != v) father[u] = v ;
}int  _in[maxn] , _out[maxn] , _vis[maxn] ;
char word[1008] ;int   gao(){int connet = 0 ;for(int i = 0 ; i < 26 ; i++){if(_vis[i] && i == getf(i))  connet++ ;}if(connet > 1) return 0 ;int e[maxn] , k = 0 ;for(int i = 0 ; i < 26 ; i++){if(_vis[i] && _out[i] != _in[i]) e[k++] = i ;}if(k == 0) return 1 ;if(k == 2){int u = e[0] , v = e[1] ;if(_out[u]==_in[u]+1 && _in[v]==_out[v]+1) return 1 ;if(_out[v]==_in[v]+1 && _in[u]==_out[u]+1) return 1 ;}return 0 ;
}int  main(){int t , n  ;cin>>t ;while(t--){cin>>n ;memset(_in , 0 , sizeof(_in)) ;memset(_out , 0 , sizeof(_out)) ;memset(_vis , 0 , sizeof(_vis)) ;for(int i = 0 ; i < 26 ; i++) father[i] = i ;while(n--){scanf("%s" , word) ;int u = word[0] - 'a' ;int v = word[strlen(word) - 1] - 'a' ;_out[u]++ ;_in[v]++ ;_vis[u] = _vis[v] = 1 ;_merge(u , v) ;}if(gao()) puts("Ordering is possible.") ;else  puts("The door cannot be opened.") ;}return 0 ;
}

POJ 2513 无向图

struct  TNode{int id ;TNode *next[26] ;TNode(){id = 0 ;for(int i = 0 ; i < 26 ; i++)  this->next[i] = NULL ;}
};int  ID ;int  _Hash(TNode *root , char *s){if(root == NULL || s == NULL)  return -1 ;TNode *now = root ;while(*s != '\0'){if(now->next[*s - 'a'] == NULL){TNode *nd = new TNode() ;now->next[*s - 'a'] = nd ;now = nd ;}else  now = now->next[*s - 'a'] ;s++ ;}if(now->id) return now->id ;return  now->id = ++ID ;
}void  _Clear(TNode *root){for(int i = 0 ; i < 26 ; i++){if(root->next[i] != NULL) _Clear(root->next[i]) ;}free(root) ;
}char wd[18] , wd2[18] ;const int maxn = 510010 ;
int  father[maxn] ;int  getf(int x){if(x == father[x]) return x ;else return father[x] = getf(father[x]) ;
}void _merge(int u , int v){u = getf(u) ;v = getf(v) ;if(u != v) father[u] = v ;
}int  degree[maxn] ;//无向图
int  gao(){int f = getf(1) ;int ct = 0 ;for(int i = 1 ; i <= ID ; i++){if(f != getf(i)) return 0 ;if((degree[i] % 2) == 1) ct++ ;if(ct > 2) return 0 ;}return 1 ;
}int  main(){freopen("test.txt" , "r" , stdin) ;TNode *root = new TNode() ;memset(degree , 0 , sizeof(degree)) ;for(int i = 0 ; i < maxn ; i++) father[i] = i ;ID = 0 ;while(scanf("%s%s" , wd , wd2) != EOF){int u = _Hash(root , wd) ;int v = _Hash(root , wd2) ;degree[u]++ ;degree[v]++ ;_merge(u , v) ;}if(gao()) cout<<"Possible"<<endl ;else  cout<<"Impossible"<<endl;_Clear(root)  ;return 0 ;
}

这篇关于HDUPlay on Words的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---