6-16 单词 uva10129

了解了欧拉回路和欧拉道路的性质 ：

欧拉道路  最多只有两个奇点（不可能只有一个奇点）     并且当有两个奇点的时候  一个奇点入比出多一   一个奇点出比入多一

采用并查集查看是否连同   如果连通块大于等于2  显然不成立

然后判断 入数组 和出数组的个数  当处于个数不相同的时候说明有奇点   判断此时一个为入奇点 一个为出奇点！！

十分巧妙

根据查找连通性不同  有两种方式：

并查集

#include<bits/stdc++.h>

using namespace std;

int f[];

int vis[];

int in[];

int out[];

int find1(int x)

{

    return f[x]==x?x:f[x]=find1( f[x]  );

}

void uni(int a,int b)

{

    if(find1(a)!=find1(b))

    {

        f[a]=b;

    }

}

char m1[][];

char m2[][];

int main()

{

    int cas;cin>>cas;

    while(cas--)

    {

      int n;cin>>n;

      memset(vis,,sizeof(vis));

      memset(in,,sizeof(in));

      memset(out,,sizeof(out));

      for(int i=;i<;i++) f[i]=i;

      string s;getchar();

      while(n--)

      {

          getline(cin,s);

          in[s[]-'a' ]++;  out[s[s.size()-]-'a'   ]++;

          vis[ s[]-'a'  ]=vis[ s[s.size()-]-'a'  ]=;

          uni( f[s[]-'a'],f[s[s.size()-]-'a' ]);

      }

        int cnt=;

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

        {

            if(vis[i]&&f[i]==i)cnt++;

        }

        if(cnt>=){printf("The door cannot be opened.\n");continue;}

        int ru=-,chu=-;

        int ok=;

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

        {

            if(vis[i]&&in[i]!=out[i])

            {

                if(in[i]==out[i]+&&ru==-)ru=;

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

                else ok=;

            }

        }

       if(ok)printf("Ordering is possible.\n");

       else printf("The door cannot be opened.\n");

    }

    return ;

}

DFS

#include<cstring>

#include<iostream>

#include<cstdio>

#include<cmath>

#define MAXN 100

using namespace std;

int vis[MAXN],G[MAXN][MAXN],N, T,f[MAXN],rank[MAXN], in[MAXN],out[MAXN];

void dfs(int u){

    vis[u] = true;

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

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

            dfs(i);

    }

}

int main(){

    freopen("input.txt","r",stdin);

    scanf("%d",&T);

    while(T--){

        memset(G, , sizeof(G));

        memset(in, , sizeof(in));

        memset(out, , sizeof(out));

        char str[];

        scanf("%d",&N);

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

            scanf("%s", str);

            ++G[str[]-'a'][str[strlen(str)-]-'a'];

            ++out[str[]-'a'];

            ++in[str[strlen(str)-]-'a'];

        }

        bool flag=true;

        int num1=, num2=;

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

            if(!flag) break;

            if(in[i]!=out[i]){

                if(in[i]==out[i]+) { ++num1; }

                else if(out[i]==in[i]+) { ++num2; }

                else {flag=false; break; }

            }

        }

        if(num1 && num2 && num1+num2>) flag=false;

        if(flag){

            memset(vis, , sizeof(vis));

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

                if(out[i]) { dfs(i); break; }

            bool flag2=true;

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

                if(in[i] && !vis[i]) { flag2=false; break; }

                if(out[i] && !vis[i]) { flag2=false; break; }

            }

            if(flag2) printf("Ordering is possible.\n");

            else printf("The door cannot be opened.\n");

        }

        else{

            printf("The door cannot be opened.\n");

        }

    }

    return ;

}