poj1386有向图判断是否存在欧拉回路或者欧拉路

有向图的图联通是指基图联通，也就是把有向图的边改成无向图然后看是否连通。判断联通可用dfs或者并查集。

题意就是给你n个由小写字母构成的字符串，问你能不能将这n个字符串连接起来，B能接在A后面的条件是A的最后一个字母==B的第一个字母。

然后就是将26个小写字母看成顶点集，对于一个字符串，其首字母向尾字母连一条单向边构图。

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int in[N],out[N],ans;

char s[N*];

vector<int>G[N];

bool vis[N];

void dfs(int u)

{

    for(int i=; i<(int)G[u].size(); ++i)

    {

        if(vis[G[u][i]])

        {

            ++ans;

            vis[G[u][i]]=;

            dfs(G[u][i]);

        }

    }

}

int main()

{

    int T,n;

    for(scanf("%d",&T); T--;)

    {

        scanf("%d",&n);

        memset(vis,,sizeof(vis));

        memset(in,,sizeof(in));

        memset(out,,sizeof(out));

        for(int i=; i<; ++i) G[i].clear();

        int cont=ans=;

        while(n--)

        {

            scanf("%s",s);

            int st=s[],ed=s[strlen(s)-];

            st-='a',ed-='a';

            G[st].push_back(ed);

            G[ed].push_back(st);

            ++in[ed];

            ++out[st];

            if(!vis[st]) ++cont;vis[st]=;

            if(!vis[ed]) ++cont;vis[ed]=;

        }

        for(n=; n<; ++n) if(!G[n].empty()) break;

        vis[n]=,++ans;

        dfs(n);

        if(ans!=cont)

        {

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

            continue;

        }

        bool ok=,k1=,k2=;

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

        {

            if(in[i]==out[i]) continue;

            else if(in[i]-out[i]==&&!k1) k1=;

            else if(out[i]-in[i]==&&!k2) k2=;

            else

            {

                ok=;

                break;

            }

        }

        if(ok) puts("Ordering is possible.");

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

    }

}