104742024-04-03 09:09:30UVinceKritikus munkákcpp17Wrong answer 0/100108ms34896 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){
    vis[v]=true;
    for (int to:adj[v]){
        if (!vis[to]) dfs(to);
    }
}

void bridge(int v,int p=-1){
    int cnt=0;
    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 {
            bridge(to,v);
            low[v]=min(low[v],low[to]);
            if(low[to]>=tin[v] && v!=1) ans.insert(v);
            cnt++;
        }
    }
    if (cnt>1 && v==1) ans.insert(1);
}

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++;
    }
    dfs(1);

    for (int i=1;i<=n;i++){
        if (!vis[i] && !adj[i].empty()){
            cout<<"0\n";
        }
    }
    vis.assign(MAXN,false);

    bridge(1);
    vector<int> be,ki;
    for (int i=1;i<=n;i++){
        if (adj[i].empty()) continue;
        if (fok[i].first==0) be.push_back(i);
        if (fok[i].second==0) ki.push_back(i);
    }
    if (be.size()==1) ans.insert(be[0]);
    if (ki.size()==1) ans.insert(ki[0]);
    cout<<ans.size()<<"\n";
    for (int i : ans) cout<<i<<" ";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms9468 KiB
2Wrong answer71ms18200 KiB
subtask20/25
3Wrong answer6ms11624 KiB
4Wrong answer6ms11868 KiB
5Wrong answer6ms11960 KiB
6Accepted6ms12076 KiB
7Accepted7ms12904 KiB
subtask30/25
8Accepted21ms15572 KiB
9Wrong answer12ms14424 KiB
10Wrong answer13ms14696 KiB
11Wrong answer16ms15700 KiB
12Wrong answer17ms15496 KiB
subtask40/25
13Wrong answer59ms27040 KiB
14Wrong answer52ms21904 KiB
15Accepted54ms25112 KiB
16Accepted50ms23312 KiB
17Wrong answer52ms22628 KiB
subtask50/25
18Wrong answer108ms27392 KiB
19Wrong answer101ms27292 KiB
20Wrong answer103ms28884 KiB
21Wrong answer97ms27864 KiB
22Wrong answer107ms34896 KiB