一笔画--PTA

题目描述

输入样例1
3 2
1 2
2 3
输出样例1
Y

输入样例2
4 3
1 2
1 3
1 4
输出样例2
N

输入样例3
1 0
输出样例3
Y

思路

dfs 、欧拉通路、欧拉回路的判定

前导知识

欧拉通路、欧拉回路、欧拉图
无向图：
①设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路
②如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路
有向图：
①设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向欧拉通路
②如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路
总结：
欧拉通路就是从点①出发，到点②，（①②不一定相同）经过该连通图所有路径仅一次；
欧拉回路就是点①和点②一定相同

欧拉通路的判定
①无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的
②有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度

欧拉回路的判定
①无向图：图连通，所有顶点都是偶数度。
②有向图：图连通，所有的顶点出度=入度。

存储结构
1.二维数组g存储图
2.一维数组cnt统计每个点的度数
3.一位数组vis标记每个数组是否被访问过

具体做法
1.使用邻接矩阵构建图，同时统计每个点的度数
2.该图可以一笔画，肯定存在欧拉通路或者欧拉回路，二者都要考虑，根据前面无向图欧拉通路和欧拉回路的判定知，需要首先满足度数条件，否则该图肯定不能一笔画
3.从每个点进行一次dfs，判断图是否可以连通

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N]; //存储节点间的关系
bool vis[N]; //标记每个点是否都被访问过
int cnt[N]; //统计每个点的度数
int num; //统计度数为奇数的点的个数
bool flag; //标记是否可以一笔画
int n, m;

void dfs(int x)
{
    for(int i = 1; i <= n; i ++)
    {
        if(g[x][i] && !vis[i])
        {
            vis[i] = true;
            dfs(i);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = 1;
        g[y][x] = 1;
        cnt[x] ++;
        cnt[y] ++;
    }
    
    for(int i = 1; i <= n; i ++)
    {
        if(cnt[i] % 2 == 1) num ++;
    }

    if(num != 2 && num != 0) printf("N\n"); //不满足存在欧拉通路 或者 欧拉回路的条件
    else
    {
        for(int i = 1; i <= n; i ++)
        {
            memset(vis, false, sizeof(vis));
            vis[i] = true; //起点初始化为访问过
            flag = true; //假设本次从i出发可以一笔画完
            dfs(i);
            for(int j = 1; j <= n; j ++)
            {
                if(!vis[j])
                {
                    flag = false;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}

欢迎大家批评指正！！！