104752024-04-03 09:19:22UVinceKritikus munkákcpp17Accepted 100/100104ms28432 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<<" ";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms9372 KiB
2Accepted65ms16064 KiB
subtask225/25
3Accepted6ms9920 KiB
4Accepted6ms10064 KiB
5Accepted7ms10072 KiB
6Accepted6ms10204 KiB
7Accepted8ms10752 KiB
subtask325/25
8Accepted20ms12796 KiB
9Accepted12ms11584 KiB
10Accepted12ms11696 KiB
11Accepted17ms12220 KiB
12Accepted17ms12180 KiB
subtask425/25
13Accepted56ms19984 KiB
14Accepted52ms18580 KiB
15Accepted50ms19104 KiB
16Accepted50ms19552 KiB
17Accepted50ms19592 KiB
subtask525/25
18Accepted104ms25720 KiB
19Accepted103ms25948 KiB
20Accepted97ms26312 KiB
21Accepted97ms27144 KiB
22Accepted94ms28432 KiB