哥尼斯堡的“七桥问题”

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

1

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

0

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

vector<int> v[MAXSIZE];   //用于存放每个点与哪个点连接
int pre[MAXSIZE];   //并查集数组,用于存放每个元素的父节点

int Find(int x)     //并查集搜索
{
    if(pre[x] == -1)   //判断是不是老祖宗
    {
        return x;
    }
    else
    {
        return pre[x] = Find(pre[x]);
    }
}

void link(int x,int y)   //判断是否联通,不连通就合并
{
    if(Find(x)!=Find(y))  //如果不连通，就把它们所在的连通分支合并
    {
        pre[Find(y)] = Find(x);
    }
}

int main()
{
    ios::sync_with_stdio(false);   //取消cin和stdin的同步
    int N,M;  //结点数N,边数M
    cin >> N >> M;
    memset(pre,-1,sizeof(pre));  //并查集数组初始化
    int a,b;
    for (int i = 1; i <= M; i++)   //输入第i条边直接联通的俩个节点的编号
    {
        cin >> a >> b;
        link(a,b);     //连接
        //把对方分别放进自己的数组
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int count = 0;  //count用来统计奇数点(与其他点有奇数个连接)
    int num = 0;    //num用来统计老祖宗个数，老祖宗有且仅有一个说明是连通图
    for (int i = 1; i <= N; i++)
    {
        if (v[i].size() % 2)
        {
            count++;
        }
        if (Find(i) == i)
        {
            num++;
        }
    }
    if (count == 0 && num == 1)   //当奇数点不存在且只有一个老祖宗时,是欧拉回路
    {
        cout << 1 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}