欧拉回路与欧拉路径

什么叫颓，我是彻底明白了。

定义：

欧拉路径：在一个图中，由i点出发，将每个边遍历一次最终到达j点的一条路径。

欧拉回路：i=j时的欧拉路径。（也就是把所有边绕一边，最后回到自己）。

判断欧拉回路：

无向图：每个点的度数为偶数（两只手才能成环，一只手咋成环呢）

有向图：每个点的入度等于出度（一个出去，一个进来）

判断欧拉路径：

无向图：有且仅有两个点度数为奇数

有向图：最多有一点入度等于出度+1，最多有一点入度等于出度-1。

例题：P1341 无序字母对

#include<cstdio> 
#include<string>
#include<iostream>
#include<stdlib.h>
using namespace std;
const int maxn=10010;
int n;
char ct[maxn];
char ans[maxn];
int map[200][200];
int deep[200];
int fa[200];
int cnt,head;
int read()//快读 
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int find(int x)//并查集 
{
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
void cz()//强联通 
{
    int strong=0;
    for (int i=64;i<=123;i++)
    if(fa[i]==i&&deep[i]) strong++;
    if(strong!=1) {
    printf("No Solution");
    exit(0);
}
}
void check()//判断欧拉路径 
{
    for(int i=64;i<=123;i++)
    {
        if(deep[i]%2==1)//奇数点 
        {
            cnt++;
            if(!head)
            head=i;
        }
    }
    if(cnt&&cnt!=2){    //有奇数点，且不为两个 
    printf("No Solution");
    exit(0);
    }  
    if(head==0)
    {
        for(int i=64;i<=123;i++)
        if(deep[i])
        {head=i;break;}
    }
    dfs(head);
    cout<<ans;
}
void dfs(int x)//来了，欧拉路径 
{
    for (int i=64;i<=123;i++)
    {
        if(map[x][i])
        {
            map[x][i]=0;
            map[i][x]=0;
            dfs(i);
        }
    }
    ans[n--]=x; //dfs是回溯的，所以倒着存 
}

void work()
{
    n=read();
    for (int i=64;i<=123;i++) fa[i]=i;
    for (int i=1;i<=n;i++)
    {
        scanf("%s",&ct);
        map[ct[0]][ct[1]]=1;
        map[ct[1]][ct[0]]=1;
        deep[ct[0]]++;
        deep[ct[1]]++;
        fa[find(ct[0])]=find(ct[1]);
    }
    cz();
    check();
}
int main()
{
    work();
    return 0;
}

欧拉回路与欧拉路径

判断欧拉路径：

相关推荐