10604 | 2024-04-06 14:24:33 | Ablablabla | Kritikus munkák | cpp17 | Accepted 100/100 | 202ms | 40152 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> csucsok;
int main()
{
int n, m;
cin >> n >> m;
csucsok.assign(n, vector<int>());
vector<int> befok(n);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--; b--;
csucsok[a].push_back(b);
befok[b]++;
}
queue<int> bejar;
vector<bool> bejart(n, 0);
vector<vector<int>> szintek(1, vector<int>());
vector<int> tav(n, 0);
for(int i = 0; i < n; i++){
if(befok[i] == 0){
bejar.push(i);
szintek[0].push_back(i);
}
}
while(!bejar.empty()){
int akt = bejar.front();
bejar.pop();
if(bejart[akt]) continue;
bejart[akt] = 1;
for(int x : csucsok[akt]){
if(bejart[x]) continue;
befok[x]--;
if(befok[x] == 0){
bejar.push(x);
tav[x] = tav[akt] + 1;
if(szintek.size() <= tav[x]){
szintek.push_back(vector<int>());
}
szintek[tav[x]].push_back(x);
}
}
}
// egyedul van a layereben
// folotte levoknek nincs kapcsolat az alatta levokkel
int maxi = 0;
vector<int> jok;
for(int i = 0; i < szintek.size(); i++){
if(szintek[i].size() == 1 && maxi <= i){
jok.push_back(szintek[i][0] + 1);
}
for(int akt : szintek[i]){
for(int x : csucsok[akt]){
maxi = max(maxi, tav[x]);
}
}
}
sort(jok.begin(), jok.end());
cout << jok.size() << "\n";
for(int x : jok){
cout << x << " ";
}
cout << "\n";
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1952 KiB | ||||
2 | Accepted | 123ms | 13244 KiB | ||||
subtask2 | 25/25 | ||||||
3 | Accepted | 3ms | 3904 KiB | ||||
4 | Accepted | 3ms | 4068 KiB | ||||
5 | Accepted | 4ms | 4468 KiB | ||||
6 | Accepted | 3ms | 4504 KiB | ||||
7 | Accepted | 6ms | 4916 KiB | ||||
subtask3 | 25/25 | ||||||
8 | Accepted | 34ms | 6560 KiB | ||||
9 | Accepted | 14ms | 6544 KiB | ||||
10 | Accepted | 14ms | 7028 KiB | ||||
11 | Accepted | 25ms | 7516 KiB | ||||
12 | Accepted | 25ms | 7828 KiB | ||||
subtask4 | 25/25 | ||||||
13 | Accepted | 83ms | 14056 KiB | ||||
14 | Accepted | 97ms | 17700 KiB | ||||
15 | Accepted | 94ms | 19876 KiB | ||||
16 | Accepted | 89ms | 21104 KiB | ||||
17 | Accepted | 90ms | 22232 KiB | ||||
subtask5 | 25/25 | ||||||
18 | Accepted | 199ms | 31640 KiB | ||||
19 | Accepted | 194ms | 35528 KiB | ||||
20 | Accepted | 202ms | 37908 KiB | ||||
21 | Accepted | 186ms | 38892 KiB | ||||
22 | Accepted | 178ms | 40152 KiB |