AC(进食后人)

虚空终端  •  28天前


注意图不一定连通,但是要保证把每一个点都找过。显然加个循环判断或者遍历起点都是可行的

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=110;

int n,T,m;
int st[N];
int g[N][N];
int q[N],h=-1,t=-1;

void bfs(int x)
{
	h=-1;
	t=-1;
	q[++t]=x;
	st[x]=1;
	while(h<t)
	{
		int p=q[++h];
		cout<<p<<' ';
		for(int i=0;i<n;i++)
		{
			if(g[p][i]==1&&st[i]==0)
			{
				st[i]=1;
				q[++t]=i;
			}
		}
	}
}

int main()
{
	cin>>T;
	while(T--)
	{		
		memset(g,0,sizeof(g));
		memset(st,0,sizeof(st));
		int t;
		cin>>n>>m>>t;
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			g[a][b]=1;
			g[b][a]=1;
		}
		bool flag=0;
		while(flag==0)
		{
			bfs(t);
			flag=1;
			for(int i=0;i<n;i++)
			{
				if(!st[i])
				{
					flag=0;
					t=i;
					break;
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

评论:

请先登录,才能进行评论