图论遇到环该怎么处理啊!(悬)
  • 板块学术版
  • 楼主DevilsFlame
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/2/23 13:52
  • 上次更新2024/2/23 15:48:04
查看原帖
图论遇到环该怎么处理啊!(悬)
1050431
DevilsFlame楼主2024/2/23 13:52

就像这题P5318 【深基18.例3】查找文献,我的代码为下,求大佬教如何处理!QAQ

#include<bits/stdc++.h>
using namespace std;
struct no{
	int a,b;
}v;
vector <no> s;
vector <int> q[100011];
queue <int> x;
int n,m,i,f;
bool e[100011];
bool cmp(no a,no b){
	if(a.b==b.b) return a.a<b.a;
	else return a.b<b.b;
}
void dfs(int x){
	printf("%d ",x);
	for(int i = 0;i < q[x].size();i ++)
	{
		if(e[q[x][i]])
		{
			e[q[x][i]] = 0;
			dfs(q[x][i]);
		}
	}
	return;
}
void bfs(int v){
	x.push(v);
	e[v] = 1;
	while(!x.empty())
	{
		v = x.front();
		x.pop();
		printf("%d ",v);
		for(i = 0;i < q[v].size();i ++)
		{
			if(!e[q[v][i]])
			{
				x.push(q[v][i]);
				e[q[v][i]] = 1;
			}
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>v.a>>v.b;
		e[v.b]=1;
		s.push_back(v);
	}
	sort(s.begin(),s.end(),cmp);
	for(i=0;i<m;i++){
		q[s[i].a].push_back(s[i].b);
	}
	for(i=1;i<=m;i++){
		if(!e[i]){
			f=i;
			break;
		}
	}
	dfs(f);
	printf("\n");
	memset(e,0,sizeof(e));
	bfs(f);
	return 0;
}
2024/2/23 13:52
加载中...