求助复杂度
  • 板块学术版
  • 楼主alex_liu
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/10/27 19:33
  • 上次更新2023/10/27 05:34:22
查看原帖
求助复杂度
373355
alex_liu楼主2022/10/27 19:33

rt,请大佬帮忙看看这时间复杂度大概是多少

#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;
}

题目:P8605

管理员要让我算时间复杂度,但这道题我是真不会

2022/10/27 19:33
加载中...