当前位置：首页 > news >正文

UVA 10129 Play on Words (欧拉通路)

news 来源：原创 2024/5/10 5:04:27

本文链接:http://www.cnblogs.com/Ash-ly/p/5398627.html

题意：

　　输入N(N <= 100000)个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同(例如:acm,malform,mouse)。每个单词最多包含 1000 个小写字母。输入中可以有重复的单词。

思路：

　　把一个字母的两端开成节点，单词看成有向边，若问题有借，当且仅当图中存在欧拉通路。所有只需要判断由单词而构建的图是否存在欧拉通路，由于是有向边，所以利用有向图欧拉通路的判定就可以了。

判定条件

(1):底图是连通图

(2):可以有两个奇点，其中一个出度比入度大 1，另外一个入度比出度大1.

对于条件1,在这里用并查集判断了,条件2统计每个点的出度，入度，加以判断就行了.

代码：

#include <stdio.h>  
#include <string.h>  
#include <iostream>  
#include <math.h>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;  

const int maxV = 29;
int m;
int pre[maxV + 7];
int outdegree[maxV + 7];
int indegree[maxV + 7];

int Find(int x){return x == pre[x] ? x : pre[x] = Find(pre[x]); }//并查集的查找
void initPre(){ for(int i = 0; i <= maxV; i++) pre[i] = i; }//初始化并查集的数组

int mix(int x, int y)//并查集的合并
{
    int fx = Find(x), fy = Find(y);    
    if(fx != fy) pre[fx] = fy;    
}

bool isConnct()//判断图是否连通，即所有的点都在一个集合里面
{
    int cnt = 0;
    for(int i = 1; i <= maxV; i++)if( (outdegree[i] != 0 || indegree[i] != 0) && pre[i] == i) cnt++;
    if(cnt == 1)return true;
    return false;
}

bool isEulur()//是否存在欧拉通路
{
    int cnt = 0;
    int flag = 0;
    for(int i = 1; i <= 26; i++)
        if((outdegree[i] != 0 || indegree[i] != 0) && (indegree[i] != outdegree[i]))//判断奇点，方法不唯一。
        {
            cnt++;
            flag += (indegree[i] - outdegree[i]);
            if(flag > 1 || flag < -1) return false;
        } 
    if(cnt == 0 || cnt == 2 && flag == 0) return true;
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &m);
        initPre();
        memset(indegree, 0, sizeof(indegree));
        memset(outdegree, 0, sizeof(outdegree));
        for(int i = 1; i <= m; i++)
        {
            char word[1000 + 7];
            scanf("%s", word);
            int u = word[0] - 'a' + 1;
            int len = strlen(word);
            int v = word[len - 1] - 'a' + 1;
            mix(u, v);
            ++outdegree[u];
            ++indegree[v];
        }
        if(isEulur() && isConnct())    printf("Ordering is possible.\n");
        else                        printf("The door cannot be opened.\n");
    }
    return 0;
}