关于图的dfs去重
  • 板块灌水区
  • 楼主caramel_qwq
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/5/21 15:12
  • 上次更新2023/10/28 00:57:53
查看原帖
关于图的dfs去重
444195
caramel_qwq楼主2022/5/21 15:12

题目大意是给定一个图(邻接矩阵就可以),然后问A点到B点的所有路径数(不允许重复)。

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1008;
int n,m,s,e,cnt=0;
bool v[MAXN][MAXN];
bool vis[MAXN][MAXN];
void dfs(int now){
	if(now==e){
		cnt++;
		return ;
	}
	for(int i=1;i<=n;i++){
		if(vis[now][i]==0&&v[now][i]==1){
			vis[now][i]=1;
			dfs(i);
			vis[now][i]=0;
		}
	}
	return ;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&e);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x][y]=1;
		v[y][x]=1;
	}
	dfs(s);
	printf("%d\n",cnt);
	return 0;
}

这份代码是会重复的,请问如何去重及去环?

2022/5/21 15:12
加载中...