10475 | 2024-04-03 09:19:22 | UVince | Kritikus munkák | cpp17 | Accepted 100/100 | 104ms | 28432 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) a.begin(),a.end()
const int MAXN=1e5+1;
vector<vector<int>> adj(MAXN);
vector<bool> vis(MAXN,false);
vector<int> tin(MAXN),low(MAXN);
int timer=0;
set<int> ans;
vector<pair<int,int>> fok(MAXN, {0,0});
void dfs(int v,int p=-1){
vis[v]=true;
tin[v]=low[v]=timer++;
for (int to : adj[v]){
if (to==p) continue;
if(vis[to]) low[v]=min(low[v], tin[to]);
else {
dfs(to,v);
low[v]=min(low[v],low[to]);
if(low[to]>=tin[v] && v!=0) ans.insert(v);
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
for (int i = 0; i < m; i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
fok[u].first++;
fok[v].second++;
}
vis.assign(MAXN,false);
for (int i=1;i<=n;i++){
if (fok[i].first==0) {
adj[i].push_back(n+1);
adj[n+1].push_back(i);
}
if (fok[i].second==0) {
adj[i].push_back(0);
adj[0].push_back(i);
}
}
dfs(0);
cout<<ans.size()<<"\n";
for (int i : ans) cout<<i<<" ";
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 6ms | 9372 KiB | ||||
2 | Accepted | 65ms | 16064 KiB | ||||
subtask2 | 25/25 | ||||||
3 | Accepted | 6ms | 9920 KiB | ||||
4 | Accepted | 6ms | 10064 KiB | ||||
5 | Accepted | 7ms | 10072 KiB | ||||
6 | Accepted | 6ms | 10204 KiB | ||||
7 | Accepted | 8ms | 10752 KiB | ||||
subtask3 | 25/25 | ||||||
8 | Accepted | 20ms | 12796 KiB | ||||
9 | Accepted | 12ms | 11584 KiB | ||||
10 | Accepted | 12ms | 11696 KiB | ||||
11 | Accepted | 17ms | 12220 KiB | ||||
12 | Accepted | 17ms | 12180 KiB | ||||
subtask4 | 25/25 | ||||||
13 | Accepted | 56ms | 19984 KiB | ||||
14 | Accepted | 52ms | 18580 KiB | ||||
15 | Accepted | 50ms | 19104 KiB | ||||
16 | Accepted | 50ms | 19552 KiB | ||||
17 | Accepted | 50ms | 19592 KiB | ||||
subtask5 | 25/25 | ||||||
18 | Accepted | 104ms | 25720 KiB | ||||
19 | Accepted | 103ms | 25948 KiB | ||||
20 | Accepted | 97ms | 26312 KiB | ||||
21 | Accepted | 97ms | 27144 KiB | ||||
22 | Accepted | 94ms | 28432 KiB |