POJ 1386 有向图欧拉通路

题意：给你一些字符串，这些字符串可以首位相接（末位置如果和另一个字符串的首位置相同的话就可以相连）。然后问你是否可以全部连起来。

思路：就是取出每个字符串的首尾位置，然后求出出度和入度，根据有向欧拉通路的性质，可以求出是否可以组成欧拉通路。

当然还得考虑一下这个图是否是连通图，这里可以用并查集记录边的集合。最后判断是否是一个连通图。

欧拉通路水题。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define clr(a) memset(a , 0 , sizeof(a) )

using namespace std ;

char a[1111] ;

struct kdq{

    int s, e ;

}al[111111] ;

int in[30] ,out[30] ;

bool vis[30] ;

int fa[30] ;

int find(int x){

    return fa[x] == x ? x : fa[x] = find(fa[x]) ;

}

void Union(int a, int b){

    a = find(a) ;

    b = find(b) ;

    if(a == b)return ;

    if(a < b)fa[b] = a ;

    else fa[a] = b ;

}

void init(){

    for (int i = 0 ; i <= 26; i ++ )fa[i] = i ;

    clr(in) ;

    clr(out) ;

    clr(vis) ;

}

int main(){

    int T ;

    cin >> T ;

    while( T -- ){

        int n ;

        cin >> n ;

        init() ;

        for (int i = 1 ; i <= n ; i ++ ){

            scanf("%s",a) ;

            int l = strlen(a) ;

            al[i].s = a[0] - 'a';

            al[i].e = a[l - 1] - 'a';

            in[a[0] - 'a'] ++ ;

            out[a[l - 1] - 'a'] ++ ;

            vis[a[0] - 'a'] = 1 ;

            vis[a[l - 1] - 'a'] = 1 ;

        }

        for (int i = 1 ; i <= n ; i ++ ){

            int u = al[i].s ;

            int v = al[i].e ;

            Union(u , v) ;

        }

        int jihe = -1 ;

        bool flag = 0 ;

        for (int i = 0 ; i < 26 ; i ++ ){

            if(!vis[i])continue ;

            if(jihe == -1){

                jihe = find(i) ;

            }

            else if(find(i) != jihe){

                flag = 1 ;

                break ;

            }

        }

        int num = 0 ;

        for (int i = 0 ; i < 26 ;i ++ ){

            if(!vis[i])continue ;

            if(abs(in[i] - out[i]) >= 2){

                flag = 1 ;

                break ;

            }

            else if(abs(in[i] - out[i]) == 1){

                num ++ ;

            }

        }

        if(flag){

            puts("The door cannot be opened.") ;

        }else

        if(num == 0 || num == 2 ){

            puts("Ordering is possible.") ;

        }else {

            puts("The door cannot be opened.") ;

        }

    }

    return 0 ;

}

巴特西

POJ 1386 有向图欧拉通路

最新文章

热门文章