有向欧拉通路

题意
 见下方汉语翻译

每叁个单词能够作为首尾七个假名相连的一条边
 然后正是输入m条边  猜度是还是不是能结成有向欧拉通路了

韦德娱乐1946手机版,有向图存在欧拉通路的充要条件:

 1.
有向图的基图连通;

 2. 任何点的出度和入度相等  也许  仅仅有几个入度和出度不对等的点
 且那两点入度与出度的差贰个为-1(源点)一个为1(终点).

揣测是还是不是衔接就是选拔并查集了

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 30, M = 100010;
struct edge{int u, v; } e[M];
int vis[N], in[N], out[N], par[N], m, ok;

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union(int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] < par[rv]) par[rv] = ru, par[ru] = tmp;
    else par[ru] = rv, par[rv] = tmp;
}

void connect()
{
    memset(par, -1, sizeof(par)); //初始化并查集
    for(int i = 0; i < m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v)) Union(u, v);
    }
    for(int i = 0; i < 26; ++i)
        for(int j = 0; j < 26; ++j)
            if(vis[i] && vis[j] && Find(i) != Find(j)) ok = 0;
}

int main()
{
    char s[1005];
    int u, v, cas;
    scanf("%d", &cas);
    while(cas--)
    {
        for(int i = 0; i < 26; ++i)
            vis[i] = in[i] = out[i] = 0;
        scanf("%d", &m);
        for(int i = 0; i < m; ++i)
        {
            scanf("%s", s);
            u = s[0] - 'a', v = s[strlen(s) - 1] - 'a';
            vis[u] = vis[v] = 1;
            e[i].u = u, e[i].v = v;
            ++in[u], ++out[v];
        }

        int id = 0, od = 0;//i[d]记录入度比出度大1的点的个数 o[d]小1
        ok = 1;
        for(int i = 0; i < 26; ++i)
        {
            if(!vis[i]) continue;
            int k = in[i] - out[i];
            if(k < -1 || k > 1) {ok = 0; break;}
            if(k == 1) ++id;
            if(k == -1) ++od;
        }
        if(id > 1 || od > 1 || id - od) ok = 0;
        connect();
        if(ok)  printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
    return 0;
}

难点描写叙述: 
多少秘门带有一个好玩的词迷。考古学家必须解开词迷才干打开门。因为从没任何格局能够打开门,因此词迷就变得十分首要。
每1个门上有成都百货上千磁盘。每3个盘上有1个单词,这一个磁盘必须又二次排列使得每一个单词第三个字
母面前八个单词后3个字母相同。比如单词”acm”能够跟在单词”moto大冢宁宁”的后面。

您的职分是
编写贰个主次,读入一组单词。然后判定是还是不是够经过整合使得每多少个单词第③个假名前边二个单
词后3个字母相同。那样才干打开门。 

输入描写叙述:

 输入文件里包涵 T
个測试数据。输入文件的首先行就是 T,接下去是 T 个測试数据。

每3个測 试数据的首先行是三个平头
N,表示单词的个数(1≤N≤一千00);接下去有 N行。每行是一个单词。每三个单词至少有 3个、至多有 1000个小写字母,即单词中单独也许出现字母’a’~’z’;在同一个測试数据中,一个单词或许出现数次。

 

出口描写叙述: 

设若通过结合单词可以达到规定的标准需求,输出”Ordering
is possible.”,不然输出”The door cannot be opened.”。 

Sample Input

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

Sample Output

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图