社区讨论

求最小上升,那就让小的最晚出现,可是有问题,希望dalao指出

P5603小 C 与桌游参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhjoe617
此快照首次捕获于
2025/11/04 05:52
4 个月前
此快照最后确认于
2025/11/04 05:52
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int n , m;
vector <int> arr[510000];
vector <int> ar[510000];
int indo[511000];
int indo2[510000];
void down(){
	priority_queue<int , vector<int> , greater < int > >que;
	for(int i=1; i<=n; i++){
		if(indo2[i] == 0)que.push(i);
	}
	stack<int>s;
	while(!que.empty()){
		int p = que.top();
		s.push(p);
		que.pop();
		for(int i=0; i<ar[p].size(); i++){
			int pos = ar[p][i];
			indo2[pos] --;
			if(indo2[pos] == 0)que.push(pos);
		}
	}
	int k = 0;
	int num = 0;
	while(!s.empty()){
		if(s.top() > k) num++;
		k = max(s.top() , k);
		s.pop();
	}
	cout << num  << '\n';
}
void uper(){
	priority_queue<int , vector<int> , greater < int > >que;
	for(int i=1; i<=n; i++){
		if(indo[i] == 0)que.push(i);
	}
	queue<int>q;
	while(!que.empty()){
		int p = que.top();
		q.push(p);
		que.pop();
		for(int i=0; i<arr[p].size(); i++){
			int pos = arr[p][i];
			indo[pos] --;
			if(indo[pos] == 0)que.push(pos);
		}
	}
	int k = 0;
	int num = 0;
	while(!q.empty()){
		if(q.front() > k) num++;
		k = max(q.front() , k);
		q.pop();
	}
	cout << num  << '\n';
}
int main(){
	cin >> n >> m;
	while(m--){
		int  l , r ;
		cin >> l >> r;
		arr[l].push_back(r);
		ar[r].push_back(l);
		indo[r]++;
		indo2[l]++;
	}
	uper();
	down();
	
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...