生活随笔
收集整理的這篇文章主要介紹了
hdu 1116 欧拉路
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
一個有向圖存在歐拉路：
在有向圖中，如果圖是弱連通的，并且圖中除開兩個頂點，其他所有頂點的入度等于出度，并且這兩個點中，一個點入度比出度多1，另一個點出度比入度少1，那么該圖存在歐拉路，這是個充要條件。
這個題中還要判斷是是否連通，用并查集 記錄判斷下即可。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;int in[50],out[50];
int root[50];void init()
{for(int i=0;i<=25;i++){root[i]=i;}
}int find(int x)
{int temp=root[x];if(x==root[x]) return x;else{return root[x]=find(root[x]);}
}int main()
{int t;scanf("%d",&t);while(t--){int n,i;init();memset(in,0,sizeof(in));memset(out,0,sizeof(out));char s[2000];scanf("%d",&n);getchar();for(i=0;i<n;i++){gets(s);int l1=strlen(s);in[s[0]-'a']++;out[s[l1-1]-'a']++;int ra=find(s[0]-'a');int rb=find(s[l1-1]-'a');if(ra!=rb) root[rb]=ra;}int flag1=0,flag2=0;int flag3=0,time=0;for(i=0;i<=25;i++){if(in[i]||out[i]){if(i==find(i))time++;}if(in[i]-out[i]==1) {flag1++;continue;}if(in[i]-out[i]==-1){flag2++;continue;}if(in[i]!=out[i]) {printf("The door cannot be opened.\n");flag3=1;break;}}if(flag3==0){if(time==1){if(flag1==0&&flag2==0) printf("Ordering is possible.\n");else if(flag1==1&&flag2==1) printf("Ordering is possible.\n");else printf("The door cannot be opened.\n");}elseprintf("The door cannot be opened.\n");}}
}
總結
以上是生活随笔為你收集整理的hdu 1116 欧拉路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
