首页 > 代码库 > HDU 1116

HDU 1116

2024-07-19 17:16:08   219人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1116

判断有向图欧拉回路和欧拉通路

有向图：

欧拉回路：图联通，所有顶点出度等于入度（通过图中每条边且只通过一次，并且经过每一顶点的回路。）

欧拉通路：图联通，除起点终点所有顶点出度等于入度，起点的出度-入度=1，终点的入度-出度=1（通过图中每条边且只通过一次，并且经过每一顶点的通路。）

图联通均用并查集判断

#include <iostream>#include <cstdio>#include <cstring>using namespace std ;int idx[100005] ;int find(int x){    return idx[x]==x?x:idx[x]=find(idx[x]) ;}int IN[100005],OUT[100005] ;char s[100005] ;int main(){    int t ;    scanf("%d",&t) ;    while(t--)    {        int n ;        scanf("%d",&n) ;        memset(IN,0,sizeof(IN)) ;        memset(OUT,0,sizeof(OUT)) ;        for(int i=0 ;i<26 ;i++)            idx[i]=i ;        int flag[30] ;        memset(flag,0,sizeof(flag)) ;        for(int i=0 ;i<n ;i++)        {            scanf("%s",s) ;            int x=s[0]-‘a‘ ;            int y=s[strlen(s)-1]-‘a‘ ;            int p=find(x) ;            int q=find(y) ;            if(p!=q)            {                idx[p]=q ;            }            flag[x]=flag[y]=1 ;            IN[x]++ ;            OUT[y]++ ;        }        int cnt=0 ;        for(int i=0 ;i<26 ;i++)        {            if(flag[i] && find(i)==i)cnt++ ;        }        if(cnt!=1)puts("The door cannot be opened.") ;        else        {            cnt=0 ;            int ans[30] ;            for(int i=0 ;i<26 ;i++)            {                if(flag[i] && IN[i]!=OUT[i])                {                    ans[cnt++]=i ;                }            }            if(!cnt)            {                puts("Ordering is possible.") ;                continue ;            }            if(cnt==2 && ((OUT[ans[0]]-IN[ans[0]]==1 && IN[ans[1]]-OUT[ans[1]]==1) || (OUT[ans[1]]-IN[ans[1]]==1 && IN[ans[0]]-OUT[ans[0]]==1)))                puts("Ordering is possible.") ;            else                puts("The door cannot be opened.") ;        }    }    return 0 ;}
View Code

 

HDU 1116


联系
我们