Blog·Tanky WooABOUTRSS

HDU/HDOJ 1116 Play on Words(并查集+欧拉通路)

08 Jan 2012
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1116

离散数学的知识,囧,这一块没怎么学,基础很薄弱啊。

不过对于欧拉回路/通路的结论,倒是不难推出。

欧拉通路:除首尾结点外,其余结点入度等于出度,起点出度减入度等于1,终点入度减出度等于1

欧拉回路:所有结点的入度都等于出度

思路:将每一个单词的首尾字母当做结点,首尾字母间连线,判断最后形成的有向图能否形成欧拉通路/回路,用并查集。

这题直接参考了网上的。

代码:

#include<stdio.h>
#include<string.h>
#define N 27
int out[N],in[N],flag[N],p[N],father[N]; 
int find(int x) 
{ 
    int r=x; 
    while(father[r]!=r) 
        r=father[r];
    return r; 
} 
void Union(int a,int b) 
{ 
    int fx,fy; 
    fx=find(a); 
    fy=find(b); 
    if(fx!=fy) 
        father[fx]=fy; 
} 
int main() 
{ 
    int i,k,cnt,a,b,ncase,n; 
    char s[1002];
    scanf("%d",&ncase); 
    while(ncase--)
    {
        for(i=0;i<26;i++)
            father[i]=i;  //初始化
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(flag,0,sizeof(flag));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            a=s[0]-'a';
            b=s[strlen(s)-1]-'a';
            Union(a,b);
            in[b]++;
            out[a]++;
            flag[a]=flag[b]=1;
        }
        cnt=0;
        for(i=0;i<26;i++)
        {
            father[i]=find(i);
            if(flag[i] && father[i]==i)
                cnt++;  //计算连通分支个数
        }
        if(cnt>1)  //不是连通图
        {
            printf("The door cannot be opened.\n");
            continue;
        }
        k=0;
        for(i=0;i<26;i++)
        {
            if(flag[i] && in[i]!=out[i])
                p[k++]=i;  //计算入度不等于出度的结点数
        }
        if(k==0)  //是欧拉回路
        {
            printf("Ordering is possible.\n");
            continue;
        }
        if(k==2 && (out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1
            || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1) )
        {   //是欧拉通路
            printf("Ordering is possible.\n");
            continue;
        }
        printf("The door cannot be opened.\n");
    } 
    return 0; 
}