萌新刚学OI,全RE,求助(P3916图的遍历),悬赏4个关注
  • 板块题目总版
  • 楼主_IOIAKer_
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/22 22:08
  • 上次更新2023/10/27 18:50:56
查看原帖
萌新刚学OI,全RE,求助(P3916图的遍历),悬赏4个关注
701289
_IOIAKer_楼主2022/7/22 22:08

萌新才学oi,求助P3916图的遍历

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 100;
int d[N] , a[N][N], flag[N] , q2[N] , q1[N] , n , m , m2 , t;
void dfs(int s)
{
	for(int i = 1;i <= n;i++)
	{
		if(a[s][i]==1 && d[i] == d[s] - 1 && flag[i]==0)
		{
			flag[i] = 1;
			q2[++t] = i;
			dfs(i);
		}
	}
}
void bfs(int x , int y)
{
	memset(d , 0x3f , sizeof(d));
	memset(flag , 0 , sizeof(flag));
	int l = 0;
	int r = 0;
	q1[++r] = x;
	d[x] = 0;
	flag[x] = 1;
	while(l < r)
	{
		int temp = q1[++l];
		if(temp == y)
			break;
		for(int i = 1;i <= n;i++)
		{
			if(a[temp][i]==1 && flag[i]==0)
			{
				q1[++r] = i;
				d[i] = d[temp] + 1;
				flag[i] = 1;
			}
		}
	}
	memset(flag , 0 , sizeof(flag));
	t = 0;
	q2[++t] = y;
	dfs(y);
	sort(q2 + 1 , q2 + t + 1);
	for(int i = 1;i <= t;i++)
		cout << q2[i] << " ";
	cout << endl;
} 
signed main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++)//原先你打成   for(int i=1;i<=n;i++)  了 
	{
		int c , b;
		cin >> c >> b;
		a[c][b] = a[b][c] = 1;
	}
	cin >> m2;
	for(int i = 1;i <= m2;i++)
	{
		int x1 , y1;
		cin >> x1 >> y1;
		bfs(x1 , y1);
	 } 
	return 0;
}

2022/7/22 22:08
加载中...