博客

欧拉路径：类似于一笔画，即可以不重复的走遍每一条边。

有向图存在欧拉路径的条件：

1.所有的点连通。

2.

（1）所有的点出度等于入度

（2）一个点满足出度 = 入度 + 1， 一个点满足入度 = 出度 + 1， 其余点满足出度 = 入度。

代码实现：

条件1：用并查集检测连通点的数量是否等于所有节点数

条件2：在输入的时候记录每个节点的入度和出度

#include<bits/stdc++.h> 

using namespace std;

const int N = 100010, M = 1000010;
int p[M], in[M], out[M], cnt[M];

int find(int x){
	if(x != p[x]) p[x] = find(p[x]);     //查找祖先
	return p[x];
}

int main( )
{
	int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i){
        p[i] = i;	
        cnt[i] = 1;                    //初始化
	} 
    while(m --){
    	int a, b;
    	cin >> a >> b;
    	if(find(a) != find(b)){		
    		cnt[find(b)] += cnt[find(a)];  //注意这两行的顺序
			p[find(a)] = find(b);          //操作针对祖先
		}
    	
    	in[b] ++;          //记录出度和入度
    	out[a] ++;
	}
    int c1 = 0, c2 = 0;        
    bool flag = true;
    if(cnt[find(1)] != n ) flag = false;
    //cout << cnt[find(1)] << endl;
    for(int i = 1; i <= n; ++ i){
    	if(in[i] - out [i] == 1) ++ c1;
    	else if(out[i] - in[i] == 1) ++ c2;
    	else if(out[i] != in[i]) flag = false;
	}
	if(!(c1 == 1 && c2 == 1 || c1 + c2 == 0)) flag = false;
	if(flag) puts("Yes");
	else puts("No");
	return 0;
}