526互联

AtCoder Beginner Contest 315 - E (toposort)

发布时间 2023-08-20 23:06:24作者: Qiansui

目录

E - Prerequisites

题意
n 本书，序号 1 ~ n。给定阅读每本书之前必须要看的书的序号。
请你输出任意一种看第一本书所需看书数量最少的方法

思路
利用拓扑序列
先对书之间的制约关系建图，再利用 bfs 找到包含书本 1 的连通块，再对全图进行拓扑排序得到拓扑序列，最后利用这个序列给出包含书本 1 的连通块的书的看书顺序，最后输出即可

本题就是靠你拓扑排序的利用。那么对于任意一本书的看书顺序均可求解。

写的时候遇到一个小问题：sort 函数比较函数利用 lambda 表达式，lambda 表达式值捕获超时，引用捕获嘎嘎快

代码

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;

void solve(){
	int n;
	cin >> n;
	int c, p;
	vector<int> e[n + 1], in(n + 1, 0);
	for(int i = 1; i <= n; ++ i){
		cin >> c;
		while(c --){
			cin >> p;
			e[i].push_back(p);
			++ in[p];
		}
	}
	//bfs
	vector<bool> f(n + 1, false);
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(auto v : e[u]){
			if(!f[v]){
				f[v] = true;
				q.push(v);
			}
		}
	}
	//topo
	for(int i = 1; i <= n; ++ i){
		if(in[i] == 0) q.push(i);
	}
	vector<int> order(n + 1), t;
	while(!q.empty()){
		int u = q.front(); q.pop();
		t.push_back(u);
		for(auto v : e[u]){
			-- in[v];
			if(in[v] == 0) q.push(v);
		}
	}
	//ans
	for(int i = 0; i < n; ++ i){
		order[t[i]] = i;
	}
	vector<int> ans;
	for(int i = 2; i <= n; ++ i)
		if(f[i]) ans.push_back(i);
	sort(ans.begin(), ans.end(), [&](int x, int y){
		return order[x] > order[y];
	});
	int len = ans.size();
	for(int i = 0; i < len; ++ i){
		cout << ans[i] << " \n"[i == len - 1];
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}