10475 2024. 04. 03 09:19:22 UVince Kritikus munkák cpp17 Elfogadva 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<<" ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 6ms 9372 KiB
2 Elfogadva 65ms 16064 KiB
subtask2 25/25
3 Elfogadva 6ms 9920 KiB
4 Elfogadva 6ms 10064 KiB
5 Elfogadva 7ms 10072 KiB
6 Elfogadva 6ms 10204 KiB
7 Elfogadva 8ms 10752 KiB
subtask3 25/25
8 Elfogadva 20ms 12796 KiB
9 Elfogadva 12ms 11584 KiB
10 Elfogadva 12ms 11696 KiB
11 Elfogadva 17ms 12220 KiB
12 Elfogadva 17ms 12180 KiB
subtask4 25/25
13 Elfogadva 56ms 19984 KiB
14 Elfogadva 52ms 18580 KiB
15 Elfogadva 50ms 19104 KiB
16 Elfogadva 50ms 19552 KiB
17 Elfogadva 50ms 19592 KiB
subtask5 25/25
18 Elfogadva 104ms 25720 KiB
19 Elfogadva 103ms 25948 KiB
20 Elfogadva 97ms 26312 KiB
21 Elfogadva 97ms 27144 KiB
22 Elfogadva 94ms 28432 KiB