社区讨论

20RE求助(玄关)

P5318【深基18.例3】查找文献参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lwj6w6kz
此快照首次捕获于
2024/05/23 19:48
2 年前
此快照最后确认于
2024/05/23 21:34
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int to,w,nxt;
}edge[100001];
int cnt,u,v,m,n,g[1001][1001],b[100001],que[100001],head,tail;
bool vis[100001];
void dfs(int cur){
	b[++cnt]=cur;
	vis[cur]=1;
	for(int i=1;i<=n;i++){
		if(g[cur][i]&&!vis[i]){
			dfs(i);
		}
	}
}
void bfs(int cur){
	head=1;tail=2;
	que[head]=cur;vis[cur]=1;
	while(head<tail){
		cur=que[head];
		for(int i=1;i<=n;i++){
			if(g[cur][i]&&!vis[i]){
				que[tail++]=i;
				vis[i]=1;
			}
			if(tail>n) break;
		}
		head++;
	}
	for(int i=1;i<tail;i++){
		cout<<que[i]<<" ";
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		g[u][v]=1;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs(i);
	}
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++){
		if(!vis[i]) bfs(i);
	}
	return false;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...