欧拉回路

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1559 字
若干组数据，每组给N个点M条无向边，判断是否
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1529
// 题意：若干组数据，每组给 N 个点 M 条无向边，判断是否存在欧拉回路（每条边恰好走一次并回到起点），N 为 0 时结束，存在输出 1 否则输出 0。
// 思路：欧拉回路的充要条件是图连通且每个点的度数都是偶数，用并查集或 DFS 判连通、用一个度数数组判奇偶即可。
// 1. 必须先判度数再看连通，两者都满足才输出 1，只满足一个都不行。
// 2. 从任意一个点出发做一次 BFS，只要访问到的点数等于 N 就说明全图连通，注意 N 个点都要算，孤立点会让图不连通。
// 复杂度：O(N + M) 时间 / O(N + M) 空间
// 易错点：每组数据都要重新初始化度数与访问数组，只清空边表会把上一组的度数带进来。
// 易错点：输入结束标志是 N 为 0，此时这一行只有 N 没有 M，读到 0 之后不能再往下读 M。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
vector<int> g[MAXN];
int deg[MAXN];
bool vis[MAXN];
int main(){
    int N;
    while(cin >> N){
        if(N == 0) break;
        int M;
        cin >> M;
        for(int i = 1; i <= N; i++){
            g[i].clear();
            deg[i] = 0;
            vis[i] = false;
        }
        for(int i = 0; i < M; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
            deg[a]++;
            deg[b]++;
        }
        bool ok = true;
        for(int i = 1; i <= N; i++){
            if(deg[i] % 2 != 0) ok = false;
        }
        queue<int> q;
        q.push(1);
        vis[1] = true;
        int cnt = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int k = 0; k < (int)g[u].size(); k++){
                int v = g[u][k];
                if(vis[v]) continue;
                vis[v] = true;
                cnt++;
                q.push(v);
            }
        }
        if(cnt != N) ok = false;
        cout << (ok ? 1 : 0) << "\n";
    }
    return 0;
}
欧拉回路

正文

一本通·提高篇的其它内容
