哥尼斯堡的“七桥问题” (25分)

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。

这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
输入格式:

输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。
输出格式:

若欧拉回路存在则输出1，否则输出0。
输入样例1:

6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6

输出样例1:

1

输入样例2:

5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4

输出样例2:

0

这道题说实话,我想过暴力把每一种顶点开头的情况都判断一下是不是能回到,后来代码写不出来,时间复杂度也太高,不过我万万没想到,判断欧拉回路是否存在竟然可以直接用大二上学期学过的离散数学里面的定理去判断,瞬间懵了.

判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。

//
// Created by TIGA_HUANG on 2020/9/24.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
bool inq[1005];
vector<int> G[1005];
int degree[1005];
int inq_cnt = 0;
void bfs(int s) {
    queue<int> q;
    q.push(s);
    inq[s] = true;
    inq_cnt++;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (unsigned int i = 0; i < G[t].size(); ++i) {
            if (inq[G[t][i]]) {
                continue;
            }
            q.push(G[t][i]);
            inq[G[t][i]] = true;
            inq_cnt++;
            if (inq_cnt == N) {
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> M;
    int v, v2;
    for (int i = 0; i < M; ++i) {
        cin >> v >> v2;
        G[v].push_back(v2);
        degree[v2]++;
        degree[v]++;
        G[v2].push_back(v);
//        in_degree[v]++;
//        out_degree[v2]++;
    }
    bfs(1);
    if (inq_cnt != N) {     /*图不连通,一定没有欧拉回路*/
        cout << '0';
        return 0;
    }
    for (int i = 1; i <= N; ++i) {
        if (degree[i] % 2) {
            cout << '0';    /*存在一个点出度不等于入度,一定不是欧拉图*/
            return 0;
        }
    }
    cout << '1';
    return 0;
}