posts - 33,  comments - 33,  trackbacks - 0
Poj 1386 欧拉回路
题意：如果单词A的结尾字母与单词B的首字母相同，那么可以认为是A到B相通。给出一系列单词，求这些词按照某种排列能否串通。
题解：
如果直接按照题意建模，以单词为顶点，边表示两两相通，那么将会得到哈密顿回路模型。显然是很难解的。
换一种方式，以字母为顶点，边表示传送的单词，那么就得到欧拉回路模型的图，可以按照欧拉定理求解。
以下给出Euler图的相关知识：
Euler回路：G中经过每条边一次且仅一次的回路
Euler路径：G中经过每条边一次且仅一次的路径
无向图存在Euler回路定理：当它是连通图+顶点度数为偶数
无向图存在Euler路径定理：当它是连通图+除两个顶点度为奇数外，其余为偶数
有向图存在Euler回路定理：当它是连通图+顶点入度 == 出度
有向图存在Euler路径定理：当它是连通图+除一个顶点的入度和出度的差的绝对值小1外，其余相等
代码：
#include <stdio.h>
#include <string.h>
const int N = 30;

class UnionSet
{
private:
    int parent[N];
    int rank[N];
    int size;
public:
    UnionSet(int _size):size(_size)
    {
        init();
    }
    ~UnionSet()
    {
    }

    void init()
    {
        for(int i = 0; i < size; ++i)
        {
            parent[i] = -1;
            rank[i] = 1;
        }
    }

    int root(int _x)
    {
        int r = _x;
        while(parent[r] >= 0)
            r = parent[r];
        int i = _x;
        int j;
        while(parent[i] >= 0)
        {
            j = parent[i];
            parent[i] = r;
            i = j;
        }
        return r;
    }

    int Union(int _r1,int _r2)
    {
        if(_r1 == _r2)
            return _r1;
        else
        {
            int root1 = root(_r1);
            int root2 = root(_r2);
            if(root1 == root2)
                return root1;
            if(rank[root1] > rank[root2])
            {
                parent[root2] = root1;
                rank[root1] += rank[root2];
            }
            else
            {
                parent[root1] = root2;
                rank[root2] += rank[root1];
            }
        }
    }
    int getRank(int _x)
    {
        return rank[_x];
    }
};
char buf1[1024];

void Test()
{
    int In[30] = {0};
    int Out[30] = {0};
    bool visited[30] = {false};
    UnionSet Set(28);
    int n;
    scanf("%d",&n);
    bool flag = false;
    int start = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%s",buf1);
        int len = strlen(buf1);
        Set.Union(buf1[0] - 'a',buf1[len-1] - 'a');
        In[buf1[len-1] - 'a']++;
        Out[buf1[0] - 'a']++;
        visited[buf1[0] - 'a'] = true;
        visited[buf1[len-1] - 'a'] = true;
        if (!flag)
        {
            start = buf1[0] - 'a';
            flag = true;
        }
    }
    
    for (int i = 0; i < 26; ++i)
    {
        if (i != start)
        {
            if (visited[i] && (Set.root(start) != Set.root(i)))
            {
                printf("The door cannot be opened.\n");
                return;
            }
        }
    }
    int cntIn = 0;
    int cntOut = 0;
    for (int i = 0; i < 26; ++i)
    {
        if (visited[i])
        {
            if (In[i] != Out[i])
            {
                if (In[i] - Out[i] == -1)
                {
                    cntIn++;
                }
                else if (In[i] - Out[i] == 1)
                {
                    cntOut++;
                }
                else
                {
                    printf("The door cannot be opened.\n");
                    return;
                }
            }
        }
    }
    if ((cntIn != cntOut)||((cntIn == cntOut)&&(cntIn > 1)))
    {
        printf("The door cannot be opened.\n");
    }
    else
        printf("Ordering is possible.\n");
}

int main()
{
    //freopen("data.txt","r",stdin);
    int tc;
    scanf("%d",&tc);
    for (int i = 0; i < tc; ++i)
    {
        Test();
    }
    return 0;
}

posted on 2011-06-02 11:56 bennycen 阅读(1527) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by:
C++博客
Copyright ©2024 bennycen