UVA 10129 Play on Words (欧拉通路)

本文链接: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 = ;

int m;

int pre[maxV + ];

int outdegree[maxV + ];

int indegree[maxV + ];

int Find(int x){return x == pre[x] ? x : pre[x] = Find(pre[x]); }//并查集的查找

void initPre(){ for(int i = ; 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 = ;

    for(int i = ; i <= maxV; i++)if( (outdegree[i] !=  || indegree[i] != ) && pre[i] == i) cnt++;

    if(cnt == )return true;

    return false;

}

bool isEulur()//是否存在欧拉通路

{

    int cnt = ;

    int flag = ;

    for(int i = ; i <= ; i++)

        if((outdegree[i] !=  || indegree[i] != ) && (indegree[i] != outdegree[i]))//判断奇点，方法不唯一。

        {

            cnt++;

            flag += (indegree[i] - outdegree[i]);

            if(flag >  || flag < -) return false;

        }

    if(cnt ==  || cnt ==  && flag == ) return true;

    return false;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &m);

        initPre();

        memset(indegree, , sizeof(indegree));

        memset(outdegree, , sizeof(outdegree));

        for(int i = ; i <= m; i++)

        {

            char word[ + ];

            scanf("%s", word);

            int u = word[] - 'a' + ;

            int len = strlen(word);

            int v = word[len - ] - 'a' + ;

            mix(u, v);

            ++outdegree[u];

            ++indegree[v];

        }

        if(isEulur() && isConnct())    printf("Ordering is possible.\n");

        else                        printf("The door cannot be opened.\n");

    }

    return ;

}