HDU 1878 欧拉回路(无向图)

欧拉路与欧拉回路

欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次

欧拉回路：起点也是终点的欧拉路（也属于欧拉路，如同正方形属于矩形）

判断

无向图的判断：

欧拉回路：每个顶点的度都为偶数

欧拉路：只有两个顶点度的个数为奇数，其余的都为偶数

有向图的判断：

欧拉回路：每个顶点的出度于入度都相等

欧拉路：一个出度 - 入度 == 1，一个入度 - 出度 == 1，其余点出度==入度

前提：图是连通的

判连通：

1. DFS：若图能连通，那么能访问完所有图中节点
2. 并查集

HDU 1878 欧拉回路

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;

int n, m;
int cnt[N];
//int tot, ans[N];
bool mp[N][N], vis[N];

void DFS(int num)
{
    vis[num] = 1;
    for(int i = 1; i <= n; ++i)
        if(mp[num][i])
        {
            mp[num][i] = mp[i][num] = 0;
            DFS(i);
//            ans[++tot] = i;
        }
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        scanf("%d", &m);
        memset(cnt, 0, sizeof(cnt));
//        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        memset(mp, 0, sizeof(mp));
//        tot = 0;
        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            mp[u][v] = mp[v][u] = 1;
            cnt[u]++, cnt[v]++;
        }
        DFS(1);
        bool flag = 0;
        for(int i = 1; i <= n; ++i)
            if(!vis[i])
            {
                flag = 1;
                cout << '0' << '\n';
                break;
            }
        if(flag)
            continue;

        flag = 0;
        int num = 0;
        for(int i = 1; i <= n; ++i)
            if(cnt[i] & 1)
            {
                flag = 1;
                cout << '0' << '\n';
                break;
            }
        if(!flag)
            cout << '1' << '\n';
    }
    return 0;
}

多用了一个ans数组存路径时会TLE