欧拉回路

/*
*直接判断各个点的度数是不是偶数，默认是连通的？？🤣🤣 */

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3;
int du[maxn+5];
int n, m;

bool isAllEven()
{
    for(int i = 1;i <= n; i++)
    {
        if(du[i] & 1) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int u, v;
    while(cin >> n >> m)
    {
        fill(du+1, du+n+1, 0);
        for(int i = 1;i <= m; i++)
        {
            cin >> u >> v;
            du[u]++; du[v]++;
        }
        cout << isAllEven() << "\n";
    }
    return 0;
}

判断各个节点的度是否为偶数，自环增加度为2，不影响，所以可以加上去

while True:
    try:
        n,m = list(map(int, input().split()))
        if n == 0:
            break
        nodes = [0 for i in range(n+1)]
        for i in range(m):
            temp = list(map(int, input().split()))
            nodes[temp[0]] += 1
            nodes[temp[1]] += 1
        whetherEuler = True
        for i in range(1,n+1):
            if nodes[i] % 2 == 1:
                whetherEuler = False
                break
        if whetherEuler:
            print(1)
        else:
            print(0)
    except Exception:
        break

#include <stdio.h>
#include <string.h>

#define MAX 1010

int degree[MAX];
int father[MAX];

int find(int x)
{
    if(father[x]==x) return x;
    else
    {
        int tmp=find(father[x]);
        father[x]=tmp;
        return tmp;
    }
}

int main()
{
    int N,M;
    int a,b;
    int i;
    while(scanf("%d",&N)!=EOF&&N)
    {
        scanf("%d",&M);
        int flag=1;
        memset(degree,0,sizeof(degree));
        for(i=1;i<=N;i++)
        {
            father[i]=i;
        }
        int temp=0;
        for(i=0;i<M;i++)
        {
            scanf("%d %d",&a,&b);
            degree[a]++;
            degree[b]++;
            temp=a;
            a=find(a);
            b=find(b);
            if(a!=b)
            {
                father[a]=b;
            }
        }
        for(i=1;i<=N;i++)
        {
            if(degree[i]%2==1)
            {
                flag=0;
                break;
            }
        }
        if(temp==0||flag==0) //先保证所有结点的度数都为偶数，并且图中至少存在边
        {
            printf("0\n");
            continue;
        }
        int root=0;
        for(i=1;i<=N;i++) //再判断图是否存在且仅存在一个连通子图（不计孤立点）
        {
            if(father[i]==i&&degree[i]) root++;
        }
        if(root==1) printf("1\n");
        else printf("0\n");
    }
}

	

/*也真是呵呵了。针对无向图欧拉回路的各种判别不一，我认为相对正确的一种说法是下面这种：

	无向图存在欧拉回路的充要条件 



	一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。

为什么呵呵：这道题AC的代码也是醉了，直接判断所有顶点的度数是否都为偶数即可，
无需判断是否连通。但正常逻辑应该是先判别整个图是否连通（使用并查集），
再判别是否所有顶点度数位偶数。 代码如下，简单的mmp*/
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int N = scanner.nextInt();
            if (N == 0)
                break;
            int M = scanner.nextInt();
            int[] branch = new int[N + 1];
            for (int i = 0; i < M; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                branch[a]++;
                branch[b]++;
            }
            int i = 0;
            for (i = 0; i < branch.length; i++)
                if (branch[i] % 2 == 1)
                    break;
            if (i < branch.length)
                System.out.println(0);
            else
                System.out.println(1);
        }
        scanner.close();
    }
}

确定无向图欧拉回路的充要条件：除孤立节点外，其它节点满足 1.连通 2.度为偶数

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int father[1001];
//并查集找父亲的操作
int findFather(int x){
    while(x!=father[x]){
        x = father[x];
    }
    return x;
}
//并查集合并的操作
void Union(int a, int b){
    int af = findFather(a);
    int bf = findFather(b);
    father[bf] = af;
}
 
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        int d[1001]; //节点度
        fill(d,d+1001,0);
        for(int i=0;i<=n;i++) father[i]=i; //初始化father数组
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            d[a]++;
            d[b]++;
            Union(a,b);
        }
        int tmp=0;
        for(int i=1;i<=n;i++){
            //有奇数度，应打印0
            if(d[i]%2!=0){
                tmp++;
                break;
            }
        }
        if(tmp>0){
            printf("0\n");
            continue;
        }
        int t = 1;
        for(int i=0;i<=n;i++){  //寻找一个非孤立节点，存入t
            if(d[i]!=0){
                t = i;
                break;
            }
        }
        int f = findFather(t);
        bool flag = false;
        for(int i=2;i<=n;i++){
            //既不是孤立节点，也不连通，应打印0
            if(findFather(i)!=f && findFather(i)!=i){
                flag = true;
                break;
            }
        }
        if(flag){
            printf("0\n");
            continue;
        }
        if(n!=0){
            printf("1\n");
        }
         
    }
    return 0;
}

#include<stdio.h>
int fa[10005],cnt[10005];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	int n,m,x,y,i;
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF&&n){
		scanf("%d",&m);
		for(i=0;i<10005;i++) fa[i]=i,cnt[i]=0;
		while(m--){
			scanf("%d%d",&x,&y);
			int fax=find(x),fay=find(y);
			if(fax-fay) fa[fax]=fay;
			cnt[x]++,cnt[y]++;
		}
		int f=find(1),flag=1;
		if(cnt[1]%2) flag=0;
		for(i=2;i<=n;i++)
			if((cnt[i]&&find(i)!=f)||cnt[i]%2){
				flag=0;
				break;
			}
		printf("%d\n",flag);
	}
}

/*
    欧拉回路：首先对于无向图而言，欧拉回路指的是通过所有的边有且仅有一次，然后可以回到原点的图
    需要满足两个要求：
    ①图是连通图=》采用并查集进行判断
    ②图中所有顶点的度数(入度+出度)均为偶数=》采用inDegree数组进行标记
    注意点:孤立点忽略不计(只存在单点回路的边，不不存在任何相连的边)

    需要注意一下用例：
    用例:
    7 8
    2 6
    5 4
    6 6
    2 1
    2 2
    5 6
    1 4
    5 5

    对应输出应该为:

    1

    你的输出为:

    0

    该例中很明显结点3,7是孤立的结点，但欧拉图只要求通过所有的边，然后能回到原点即可，
    因此对于孤立的点可以无需考虑，这里采用set存储非孤立的结点的编号。后续统计度数的
    奇偶性以及连通分量的个数时可以忽略这些孤立的顶点不管。
*/
#include <iostream>
#include <set>
#define N 1001
using namespace std;
int Tree[N];

int inDegree[N];
set<int> Mapping;

int findRoot(int x){
    if(Tree[x]==-1)return x;
    else{
        Tree[x]=findRoot(Tree[x]);
        return Tree[x];
    }
}

int main()
{
    int n,m;
    int a,b;
    while(~scanf("%d",&n)){
        if(n==0)break;
        scanf("%d",&m);
        for(int i=1;i<=n;i++){
            Tree[i]=-1;
            inDegree[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            if(a==b)continue;//单点回路忽略不计
            Mapping.insert(a);
            Mapping.insert(b);
            inDegree[a]++;
            inDegree[b]++;
            a = findRoot(a);
            b = findRoot(b);
            if(a!=b)Tree[a]=b;
        }
        int cnt=0;//统计连通分量的个数
        for(auto it=Mapping.begin();it!=Mapping.end();it++){
            if(Tree[*it]==-1)cnt++;
        }
        if(cnt!=1){
            printf("0\n");
        }
        else{
            int cnt1=0;//统计度数为奇数的结点个数
            for(auto it=Mapping.begin();it!=Mapping.end();it++){
                if(inDegree[*it]&1==1){
                    cnt1++;
                }
            }
            if(cnt1==0){
                printf("1\n");
            }
            else{
                printf("0\n");
            }
        }
    }
    return 0;
}
/*
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
*/

	

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define M 202
using namespace std;
typedef long long ll;
struct stack
{
    int top,node[M];
}s;
int e[M][M],n;
int icount = 0;
int visited[1000];
void DFS(int i)
{
    int j = 0;
    visited[i] = 1;
    icount++;
    for(j=0; j<n; j++)
    {
        if(e[i][j]==1 && !visited[j])//i和j有关系相邻，并且j顶点没有被访问过
        {
            DFS(j);
        }
    }
}
bool judge(){                //判断是否所有点已被遍历过
    for(int i=1;i<=n;++i)
        if(!visited[i])
            return false;
    return true;
}

int main( )
{
    int i,j,u,v,m,degree,num=0,start=0;
    scanf("%d%d",&n,&m);
    mem(e,0);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        e[u-1][v-1]=e[v-1][u-1]=1;
    }
    for(i=0;i<n;i++)
    {
        degree=0;
        for(j=0;j<n;j++)
        if(i!=j){//这的测试数据自环不能算度
            degree+=e[i][j];
        }

        if(degree&1)
        {
            start=i;
            num++;
        }
    }
    //cout<<"num "<<num<<endl;
    if((num==0)&&n<m){
          //牛客的判题数据不需要检查是不是连通图，
        //DFS(0);
        printf("%d",1);
       // if(judge())
        //    printf("%d",1);
       // else
       //     printf("%d",0);
    }

    else printf("%d",0);
    return 0;
}

//无向图判断是否有欧拉回路
//1. 联通；2. 度为0
//但是这个题还有坑的一点，就是有孤立点。按照题意度为0的孤立点对结果没有影响，但是有自环孤立点则不是欧拉图（无法一笔画）
#include <iostream>
#include<stdio.h>
using namespace std;

//点序号从1开始
const int MAXLEN=1001;
int N,M;
int root[MAXLEN];
int degree[MAXLEN];
int find_root(int x){
    if(root[x]==x)return x;
    x=find_root(root[x]);
    return x;

}

void join(int x,int y){
    int x_r=find_root(x);
    int y_r=find_root(y);
    if(x_r==y_r)return;
    root[x_r]=y_r;
}

void init(){
    for(int i=0;i<MAXLEN;++i)
    {root[i]=i;
    degree[i]=0;}

}
int main()
{
    int from,to;
    while(scanf("%d",&N)!=EOF){
        if(N==0)break;
        scanf("%d",&M);
        init();
        for(int i=0;i<M;++i){
            scanf("%d%d",&from,&to);
            join(from,to);
            degree[from]+=1;
            degree[to]+=1;
        }
        bool is_=true;
        //check connect and even
        int comp=0,r_1=find_root(1);
        for(int i=1;i<=N;++i){
            //cout<<find_root(i)<<" "<<degree[i];
            if(degree[i]==0)continue;//度为0孤立点，直接不用管
            if(find_root(i)!=r_1 || degree[i]%2!=0){
            is_=false;
                break;
            }
        }
        if(is_){
            printf("1\n");
            continue;
        }
        printf("0\n");

    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int MAX=1000;
int father[MAX];
int height[MAX];
int visitNode[MAX];
void Initial(int n){

	for(int i=0;i<=n;i++){
		father[i]=i;
		height[i]=0;
        visitNode[i]=0;
	}
	return ;
}

int Find(int x){
	if(x!=father[x]){
		father[x]=Find(father[x]);
	}
	return father[x];
}

void Union(int x,int y){
	x=Find(x);
	y=Find(y);
	if(x!=y){
		if(height[x]<height[y]){
			father[x]=y;
		}else if(height[y]<height[x]){
			father[y]=x;
		}else{
			father[y]=x;
			height[x]++;
		}
	}
	return ;
}

int main(){
	int n,m;
	while(cin>>n>>m){
		Initial(n);
		int indegree[n];
        fill(indegree,indegree+n,0);
		if(n==0) break;
		while(m--){
			int x,y;
			cin>>x>>y;
            if(x==y){
                continue;
            }
			indegree[x]++;
			indegree[y]++;
            visitNode[x]=1;visitNode[y]=1;
			Union(x,y);
		}
		int count=0,flag=0;
		for(int i=1;i<=n;i++){
			if(father[i]==i&&visitNode[i]==1){
				count++;
			}
			if(indegree[i]!=2&&visitNode[i]==1){
				cout<<"0"<<endl;
				flag=1;
				break;
			}
		}
		
		if(count==1&&flag==0){
			cout<<"1"<<endl;
		} 
	}
}

//统计每个结点的度，通过奇点（度为奇数的点）是否存在判断欧拉回路是否存在
//若奇点存在，则欧拉回路不存在，否则欧拉回路存在
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000;

vector<int>degree(MAXN);    //每个结点的度

int main() {
    int n, m;
    while (cin >> n >> m) {
        while (m--) {
            int from, to;       //起点和终点
            cin >> from >> to;
            degree[from]++;
            degree[to]++;
        }
        bool exist = true; //判断欧拉回路是否存在
        for (int i = 1; i <= n; i++) {
            if (degree[i] % 2 != 0) {
                exist = false;  //存在奇点（度为奇数的点），则不存在欧拉回路
                break;
            }
        }
        cout << static_cast<int>(exist) << endl;    //bool->int
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int *ufs = nullptr; // 并查集

int find(int a) // 查找
{
    if (a != ufs[a])
        ufs[a] = find(ufs[a]); // 路径压缩
    return ufs[a];
}

void unio(int a, int b) // 合并
{
    a = find(a);
    b = find(b);
    if(a != b)
        ufs[b] = a;
}

int main() {
    int N, M;
    while (cin >> N >> M) { // 注意 while 处理多个 case
        if(ufs) // 释放之前的用例的空间
            delete[] ufs;

        ufs = new int[N];
        int degrees[N];
        for (int i = 0; i < N; ++i) // 初始化并查集和度数
        {
            ufs[i] = i;
            degrees[i] = 0;
        }

        for(int i = 0; i < M; ++i) // 构建并查集，计算度数
        {
            int a, b;
            cin >> a >> b;
            ++degrees[a];
            ++degrees[b];
            unio(a, b);
        }
        
        int t = 0, rst = 1;
        for(int i = 0; i < N; ++i)
        {
            if(degrees[i] == 0) // 孤点
                continue;
            if(degrees[i] & 1) // 非孤点且度为奇数，不存在欧拉回路
            {
                rst = 0;
                break;
            }
            if(t == 0) // 不是孤点，且是找到的第一个连通子图，找到这个图的根
                t = find(i);
            else if(find(i) != t) // 有多个非孤点的连通子图，不存在欧拉回路
            {
                rst = 0;
                break;
            }
        }
        cout << rst << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

//由不间断的一笔画完可以想到深度优先，同时利用并查集辅助查找下一个目标城市,这是一开始的想法
//但测试用例总有一个过不了，后来看了看欧拉回路的定义才知道其他更好的做法
#include "stdio.h"
int N,M;
int father[1000];
int degree[1000];
bool isAppear[1000];

int find(int x){
    if(father[x] != x){
        father[x] = find(father[x]);
    }
    return father[x];
}

void Init(){
    for (int i = 1; i <= N; ++i) {
        father[i] = i;
        degree[i] = 0;
        isAppear[i] = false;
    }
}

int main(){
    while (scanf("%d",&N) != EOF){
        if(N == 0)
            break;
        scanf("%d",&M);
        Init();
        int c1,c2;
        for (int i = 0; i < M; ++i) {
            scanf("%d%d",&c1,&c2);
            if(c1 == c2)
                continue;
            ++degree[c1];
            ++degree[c2];
            if(find(c1) != find(c2))
                father[find(c1)] = c2;
            isAppear[c1] = true;
            isAppear[c2] = true;
        }
        int count = 0;
        for (int i = 1; i <= N; ++i) {
            if(father[i] == i && isAppear[i] == true)
                ++count;
        }
        if(count != 1)
            printf("0\n");
        else{
            count = 0;
            for (int i = 1; i <= N; ++i) {
                if(degree[i]%2 == 1)
                    ++count;
            }
            if(count == 0)
                printf("1\n");
            else
                printf("0\n");
        }
    }
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cctype>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <sstream>

using namespace std;

#pragma warning(disable:4996)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repr(i, a, b) for(int i = a; i >= (b); --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int INF = 0x3f3f3f3f;
const int maxn = 1005;
int n, m;
bool flag = false;
void dfs(vector<int> G[], int count, map<pair<int, int>, bool > &mp, int s) {
    if ((s == 1 && count == m) || flag == true) {
        flag = true;
        return;
    }
    rep(i, 0, sz(G[s]))
        if (mp[{s, G[s][i]}] == false ) {
            mp[{s,G[s][i]}] = mp[{G[s][i], s}] = true;
            dfs(G, count + 1, mp, G[s][i]);
            mp[{s,G[s][i]}] = mp[{G[s][i], s}] = false;            
        }
}
int main(){
    while (cin >> n) {
        if (n == 0)
            break;
        cin >> m;
        vector<int> G[maxn];
        rep(i, 0, m) {
            int f, t;
            cin >> f >> t;
            G[f].push_back(t);
            G[t].push_back(f);
        }
        flag = false;
        map<pair<int, int>, bool > mp;
        dfs(G, 0, mp, 1);
        cout << flag << endl;
    }
    return 0;
 }

import java.util.*;
/**
牛客这是在逗我？不连通还可以有欧拉回路？
建议这道题直接去HDU1878提交，这个测试用例不敢苟同。
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1878

1、欧拉回路充要条件：
（1）连通图
（2）所有顶点的度为偶数
-------------------------
2、欧拉通路充要条件：
（1）连通图
（2）至多有一个度为奇数的节点
*/
public class Main{
    private static int N;
    private static int M;
    private static int[] Degree;
    private static int[] father;
    public static void init(){
        for(int i = 1; i <= N; i++)
            father[i] = i;
    }
    public static int getFather(int x){
        if(father[x] != x)
            father[x] = getFather(father[x]);
        return father[x];
    }
    public static void Union(int x, int y){
        int xx= getFather(x);
        int yy = getFather(y);
        if(xx != yy)
            father[yy] = xx;
    }
    public static boolean isOlaGraph(){
        int subGraph = 0;
        for(int i = 1; i <= N; i++)
            if(father[i] == i)
                subGraph++;
        if(subGraph != 1)
            return false;
        for(int i = 1; i <= N; i++)
            if((Degree[i] & 1) == 1)
                return false;
        return true;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            N = in.nextInt();
            if(N == 0)
                break;
            M = in.nextInt();
            Degree = new int[N + 1];
            father = new int[N + 1];
            init();
            for(int i = 0; i < M; i++){
                int x = in.nextInt();
                int y = in.nextInt();
                Degree[x]++;
                Degree[y]++;
                Union(x, y);
            }
            System.out.println(isOlaGraph() ? 1 : 0);
        }
    }
}