Atcoder_[abc284E]Count Simple Paths题解

题目链接
这题就是很简单的图上深搜，我觉得放在E题太水了，代码里有详细注释。

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v[200010]; // 邻接表
int ans; // 答案
bool vis[200010]; // vis[i] 记录 i 号点有没有被访问过

void dfs(int x)
{
    if(ans >= 1e6) // 如果答案已经大于等于 1e6 ，则直接返回，因为再加都没用了，最后会被输出成 1e6
        return ;
    ans++; // 这是一条简单路径，答案加一
    for(int i = 0; i < v[x].size(); i++) // 对于 x 所能到达的所有点
    {
        if(!vis[v[x][i]]) // 如果这个点没被访问过（因为简单路径中不能出现一个点被访问 2 次的情况）
        {
            vis[v[x][i]] = true; // 将这个点设为被访问过了的状态
            dfs(v[x][i]); // 继续深搜
            vis[v[x][i]] = false; // 回溯
        }
    }
}

signed main() // 读代码的好习惯：先从 main() 函数读起
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b); // 给 a->b 建一条边
        v[b].push_back(a); // 因为是双向道，所以要再给 b->a 建一条边
    }
    vis[1] = true; // 1 号点是起点，肯定已经被访问过了
    dfs(1); // 从 1 号点开始深搜
    cout << min(ans,1000000LL) << "\n"; // 输出答案，因为题目中说了，要取 min( 答案 , 1e6)
    return 0;
}

记录

本人码风可能有点特殊，希望大家能接受。