P8605 题解

sgl654321 · 2022-11-11 19:21:28 · 题解

题目大意

给定一个 n 个节点，m 条边的无向图，没有重边和自环。

从一个起点出发，经过两个结点，到达一个终点。定义一条合法的路径，应满足经过的两个结点都只在路径中出现一次。问合法的路径个数。

解题思路

简单图论题。考虑 dfs。

遍历每一个结点为起点，进行深度优先搜索。记录遍历的路径的每一个结点。

当深度为 4 时，说明已经到达了终点。此时停止深度优先遍历，进行验证。设这一条路径经过的四个结点分别是 a_1,a_2,a_3,a_4。如果它们满足 a_1=a_2 或 a_1=a_3 或 a_2=a_3 或 a_2=a_4 或 a_3=a_4，则不是一条合法路径。如果是合法路径，则 ans 自增 1。

最后输出 ans 即可。

参考代码

使用链式前向星存图。

#include<bits/stdc++.h>
using namespace std;
bool vis[100010];
long long n,m,x,y,ans;
long long k,v[100010],nex[100010],poi[100010];
long long a[10],num[100010];
void add_edge(long long x,long long y){
    k++;v[k]=y;nex[k]=poi[x];poi[x]=k;
}//链式前向星建图
void dfs(long long dep,long long x){

    a[dep]=x;
    if(dep==4){//深度为4，进行验证。
        if(a[1]==a[2]||a[1]==a[3]||a[2]==a[3]||
        a[2]==a[4]||a[3]==a[4])return;
        //cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<endl; 
        ans++;
        return;
    }
    vis[x]=1;
    long long save=poi[x];
    while(save>0){
        dfs(dep+1,v[save]);
        save=nex[save];
    }
    vis[x]=0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        add_edge(x,y);
        add_edge(y,x); 
    }
    for(int i=1;i<=n;i++)
        dfs(1,i);
    cout<<ans<<endl;
    return 0;
}