只输出1求调
查看原帖
只输出1求调
551630
Lemon_zqp楼主2024/6/9 21:39
#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;

vector<int> g[100005], see[100005];
queue<int> q;
priority_queue<int, vector<int>, greater<int> > pq;
int deg[100005];

void init(int x){
	memset(deg, 0, sizeof(deg));
	for(int i = 1; i <= x; i++){
		g[i].clear();
	}
	for(int i = 1; i <= x; i++){
		for(int j = 0; j + 1 < see[i].size(); j++){
			int u = see[i][j];
			int v = see[i][j + 1];
			++deg[v];
			g[u].push_back(v);
		}
	}
}

bool check(int n){
	init(n);
	int num = 0;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		num++;
		for(int v: g[u]){
			if(--deg[v] == 0){
				q.push(v);
			}
		}
	}
	return (num == n);
}

void topsort(int n){
	for(int i = 1; i <= n; i++){
		if(deg[i] == 0){
			pq.push(i);
		}
	}
	while(!pq.empty()){
		int u = pq.top();
		cout << u << " ";
		pq.pop();
		for(int v: g[u]){
			if(--deg[v] == 0){
				pq.push(v);
			}
		}
	}
}

signed main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int k;
		cin >> k;
		while(k--){
			int u;
			cin >> u;
			see[i].push_back(u);
		}
	}
	int l = 1, r = m;
	while(l < r){
		int mid = (l + r + 1) / 2;
		if(check(mid)){
			l = mid;
		}
		else{
			r = mid - 1;
		}
	}
	int x = l;
	init(x);
	for(int i = 1; i <= x; i++){
		for(int v:g[i]){
			deg[v]++;
		}
	}
	topsort(x);
	return 0;
}
2024/6/9 21:39
加载中...