ABC E题求调
  • 板块学术版
  • 楼主_Richardguo_
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/8/19 22:53
  • 上次更新2023/11/3 02:33:32
查看原帖
ABC E题求调
732567
_Richardguo_楼主2023/8/19 22:53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int in[N];
vector<int>e[N],ee[N];
bool f[N];
void bfs(){
	f[1]=1;
	queue<int> q;
	q.push(1);
	while(q.size()){
		int u=q.front();q.pop();
		for(int i=0;i<ee[u].size();i++)if(!f[ee[u][i]])f[ee[u][i]]=1,q.push(ee[u][i]);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int m,x;cin>>m;in[i]+=m;
		for(int j=1;j<=m;j++)cin>>x,e[x].push_back(i),ee[i].push_back(x);
	}
	bfs();
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(!in[i]&&f[i])q.push(i);
	}
	vector<int>ans;
	while(q.size()){
		int u=q.front();q.pop();ans.push_back(u);
		for(int i=0;i<e[u].size();i++){
			in[e[u][i]]--;
			if(!in[e[u][i]])q.push(e[u][i]);
			if(e[u][i]==1&&!in[1]){
				for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
				return 0;
			}
		}
	}
	return 0;
}

WA*25

AC*12

2023/8/19 22:53
加载中...