P8605 [蓝桥杯 2013 国 AC] 网络寻路

alex_liu · 2022-10-25 10:57:15 · 题解

题目传送门

思路

统计方案数的话第一眼想到的就是 dfs 了吧，传输数据时需要传当前的节点与当前经过的节点数。

当节点数为 4 时，方案数 +1

在通过节点数为 3 的时候要特判：最后的节点也可以与第一个节点相同。

分析完这些之后，代码就很好写了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans,f;
vector<int>e[100005];//邻接表存边
bool vis[10005];
inline void dfs(int u,int step){
    if(step==4)ans++;//统计方案数
    else{
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i];
            if(!vis[v]){
                vis[v]=1;
                dfs(v,step+1);
                vis[v]=0;//注意回溯
            }
            else if(step==3&&v==f)dfs(v,step+1);//特判最后一个点与第一个点相同的情况，也就是一个环
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){//枚举每个点为起点
        vis[i]=1;
        dfs(f=i,1);
        vis[i]=0;
    }
    cout<<ans<<endl;
    return 0;
}