有向圖是否具有歐拉通路或回路的判定:
歐拉通路:圖連通;除2個端點外其余節點入度=出度;1個端點入度比出度大1;一個端點入度比出度小1 或 所有節點入度等于出度
歐拉回路:圖連通;所有節點入度等于出度
#include<stdio.h> #include < string .h> #define MAX 27 int in [MAX], out [MAX]; int visit[MAX],father[MAX]; int find( int index) { if (index==father[index]) return index; else return find(father[index]); } int main( void ) { int t,n; int i,j; int s,e; char str[ 1001 ]; scanf( " %d " ,& t); while (t-- ) { scanf( " %d " ,& n); memset(visit, 0 , sizeof (visit)); memset( in , 0 , sizeof ( in )); memset( out , 0 , sizeof ( out )); for (i= 0 ;i<MAX;i++) father[i]= i; for (i= 0 ;i<n;i++ ){ scanf( " %s " ,str); int len= strlen(str); s =str[ 0 ]- ' a ' ,e=str[len- 1 ]- ' a ' ; father[s] =father[e]= find(s); visit[s] =visit[e]= 1 ; out [s]++; in [e]++ ; } // 判斷改圖是否連通 int r= 0 ; for (i= 0 ;i<MAX;i++ ){ if (visit[i]&&i==father[i]) r++ ; } if (r> 1 ){ // aba abc printf( " The door cannot be opened.\n " ); continue ; } int x,y,z,h; x =y=z=h= 0 ; for (i= 0 ;i<MAX;i++ ){ if (visit[i]){ if ( out [i]- in [i]== 1 == 1 ) x++ ; else if ( in [i]- out [i]== 1 )y++ ; else if ( in [i]== out [i]) z++ ; else h++ ; } } if (h== 0 &&((x== 1 &&y== 1 )||(x== 0 ||y== 0 ))) printf( " Ordering is possible.\n " ); else printf( " The door cannot be opened.\n " ); } return 0 ; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
