博客

基本定义以及判断方法：图片截取自博客

HDU1878——欧拉回路（并查集）

例题1：

欧拉回路

代码：

//本题为无向图的欧拉回路
//欧拉回路:图连通；图中所有节点度均为偶数
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn = 1050;
int F[maxn], degree[maxn];
int n, m;
int Find(int x) {
    return F[x] == x ? x : F[x] = Find(F[x]);
}
void Join(int x, int y){
     int xx = Find(x);
     int yy = Find(y);
     if(xx != yy)F[xx] = yy;
}
int main(){
    while(scanf("%d", &n) && n != 0){
        scanf("%d", &m);
        memset(degree, 0, sizeof(degree));
        for(int i = 1; i <= n; i++)F[i] = i;
        for(int i = 1; i <= m; i++){
            int x, y;
            scanf("%d %d", &x, &y);
            Join(x, y);
            degree[x]++;
            degree[y]++;
        }
        int tmp = Find(1);
        int flag = 1;
        for(int i = 1; i <= n; i++){
            if(degree[i]&1)flag= 0;
            if(tmp != Find(i))flag = 0;
        }
        printf("%d\n", flag);
    }
return 0;
}

例题2：

Play on Words

代码：

//有向图的欧拉回路的判断
//欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；
//一个端点入度比出度小1 或 所有节点入度等于出度
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn = 100;
int F[maxn], in[maxn], out[maxn];
int n, m;
int Find(int x)
{
    return F[x] == x ? x : F[x] = Find(F[x]);
}
void Join(int x, int y){
     int xx = Find(x);
     int yy = Find(y);
     if(xx != yy)F[xx] = yy;
}
void Init()
{
    for(int i = 1; i <= 26; i++)
    {
        F[i] = i;
    }
}
int main()
{
    char a[1200];
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        Init();
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        for(int i = 1; i <= n; i++)
        {
            getchar();
            scanf("%s", &a);
            int x = a[0]-'a'+1;
            int len = strlen(a);
            int y = a[len-1]- 'a'+1;
            in[x]++;
            out[y]++;
            Join(x, y);
        }
        int cn = 0;
        for(int i = 1; i <= 26; i++){
            if((out[i]||in[i]) && Find(i) == i)
            cn++;
        }
        int c1 = 0, c2 = 0;
        if(cn > 1)printf("The door cannot be opened.\n");
        else {
            for(int i = 1; i <= 26; i++){
                if(in[i] == out[i])continue;
                else if(in[i] - out[i] == 1)c1++;
                else if(out[i] - in[i] == 1)c1++;
                else c2++;
            }
            if((c1 == 2 || c1 == 0) && c2 == 0)printf("Ordering is possible.\n");
            else printf("The door cannot be opened.\n");

        }

    }
    return 0;
}