反向建图+拓扑WA求调
查看原帖
反向建图+拓扑WA求调
1008614
Juan2012楼主2025/2/6 20:57
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a,in[N],lg[N],cnt,f[N];
vector<int>v[N];
void toposort(){
	queue<int>q;
	q.push(1),f[1]=1;
	while(q.size()){
		int t=q.front();
		q.pop();
		lg[++cnt]=t;
		for(int i=0;i<v[t].size();i++){
			int g=v[t][i];
			if(f[g]) continue;
			in[g]-=1;
			if(in[g]==0){
				q.push(g);
			}
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		for(int j=1;j<=m;j++){
			cin>>a,in[a]++,v[i].push_back(a);
		}
	}
	toposort();
	for(int i=cnt;i>1;i--) cout<<lg[i]<<" ";
	return 0;
}//wa*27

已经用dfs过了,但这种方法始终做不出来,求助

2025/2/6 20:57
加载中...