P6066 [USACO05JAN]Watchcow S

SCP982 · 2022-12-30 11:47:53 · 题解

需要知识点:

• 图的基础知识（有向图&无向图, 图的存储）

• 欧拉回路基础概念

  本篇用到知识点

• vector 存储

• 欧拉回路

  解析

  从 1 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 1 号农场，从一个点出发，每条边都走一遍并回到起点，这是一个经典的欧拉回路问题。由于每条路必须从两个方向各走恰好一遍，所以需要双向建边，本人没有看到任何一篇使用了 vector 存图的新手向题解，所以过来写一篇较朴实无华の新手向题解，只要知道欧拉回路和 vector 是啥就行。

  啥是欧拉回路

• 对于无向图，欧拉回路就是在图的所有结点的度都是偶数，并且图是连通的情况下，从任意一个节点开始 dfs 都可以回到原点。

• 对于有向图，欧拉回路就是在图的所有结点的出度和入度都相同，并且图是连通的情况下，从任意一个节点开始 dfs 都可以回到原点。

• 本题明确说明存在欧拉回路，所以不需要判断。

  啥是度

• 对于无向图，度就是连接节点的边数（没有 up 会给你解释这个的）

• 对于有向图，出度就以该点为起点的边的条数，入度就是以该点为终点的边的条数。

  代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v;
vector<int> ve[10002];
queue<int> ans;
//这里就是一个朴实无华的深搜，就只是用了欧拉回路的思路，反正他会回来，每次删边就行
void dfs(int f){
    int len=ve[f].size();
    for(int i=0;i<len;++i){
        int xn=ve[f][i];
        if(xn){
            //删边
            ve[f][i]=0;
            dfs(xn);
        }
    }
    //ans是用来存最终的顺序的
    ans.push(f);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        //双向建边
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    //从1号点开始dfs
    dfs(1);     
    //输出，每次输出都出队
    while(!ans.empty()) {
        printf("%d\n",ans.front());
        ans.pop();
    }
    //朴实无华的结束
    return 0;
}

对代码的补充说明

在代码第五行我使用了队列来存储最后的答案，这个方法只是偷了个懒，没有算如果用数组最多要开多大，那接下来就算一下。

首先题中明确给出了边的最大数量也就是 M（1 \leq M \leq 5 \times 10^4），又因为这里每条边要走两次，相当于 2M 条边，从起点出发，每走一条边，就会扩展一个点，再加上起点，欧拉回路最终会有 2M+1 个点，也就是 100001 个点，因为我的数组要从下标一开始存，所以数组的空间要开到 100002。