社区讨论
求最小上升,那就让小的最晚出现,可是有问题,希望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 条回复,欢迎继续交流。
正在加载回复...