uvaoj 10129 - Play on Words - dblank

uvaoj 10129 - Play on Words

传送门:10129 - Play on Words

题意:给你n个单词,只有小写字母组成,他们尾字母和其它的首字母相同的话就可以连在一起,问这个n个单词能否连在一起。

思路:有向图的欧拉路径,以首字母和尾字母为点,单词为边,则满足一个欧拉路径的条件是所有的点联通,并且全部的点入度等于出度或者只有一个入度比出度大一和只有一个入度比出度少一。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1000 + 10, Mod = 1000000009;
char s[N];
int in[100], out[100];
int root[100];
int Find(int x)
{
    return x == root[x] ? x : root[x] = Find(root[x]);
}
int join(int x, int y)
{
    int a = Find(x), b = Find(y);
    if(a!=b)
        root[a] = b;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        int n, id = 0;
        scanf("%d", &n);
        int vis[100];
        for(int i= 0; i<=26; i++ )
            vis[i] = 0, root[i] = i;
        for(int i = 0; i<n; i++)
        {
            scanf("%s", s);
            int a = s[0] - 'a';
            int b = s[strlen(s) - 1] - 'a';
            in[a]++;
            out[b]++;
            join(a, b);
            vis[a] = 1, vis[b] = 1;
        }
        int num = 0, fuck = 0, shit = 0;
        for(int i = 0; i<26; i++){
            if(in[i] != out[i])
                num++;
                if(in[i] - out[i] == 1)
                    fuck ++;
                if(out[i] - in[i] == 1)
                    shit ++;
        }
        int ok = 0;
        for(int i = 0; i<26; i++)
            if(root[i] == i && vis[i])
                ok++;
        // cout<<num<<" "<<ok<<endl;
        if((num ==0 || fuck == shit && shit == 1)&& ok == 1)
            puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    return 0;
}

 

相关文章

仅有 1 条评论
  1. VivoDrek

    The "shale revolution", obviously, thoroughly masters the minds political figures and businessmen of the world. Palm superiority this field maintain Americans, but, apparently, there is a risk that other world soon to them to join. Naturally, has state where practically is conducted production of shale gas in Russia, in particular, it endeavor the main interest of political and business elites looks enough skeptical. In this matter is not so much the factor financial profitability. Main condition that has the ability to affect possibilities such industries as craft of shale gas, - effects for environment.
    gastroparesis

    VivoDrek 回复
发表新评论