104732024-04-03 09:07:59UVinceKritikus munkákcpp17Hibás válasz 0/100109ms46948 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 (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<<" ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva6ms9468 KiB
2Hibás válasz71ms18212 KiB
subtask20/25
3Hibás válasz4ms11568 KiB
4Hibás válasz6ms11716 KiB
5Hibás válasz6ms11812 KiB
6Elfogadva4ms11960 KiB
7Elfogadva7ms12788 KiB
subtask30/25
8Elfogadva20ms15536 KiB
9Hibás válasz10ms14100 KiB
10Hibás válasz12ms14492 KiB
11Hibás válasz16ms15404 KiB
12Hibás válasz16ms15208 KiB
subtask40/25
13Hibás válasz57ms26628 KiB
14Hibás válasz52ms22152 KiB
15Elfogadva54ms26708 KiB
16Elfogadva50ms26028 KiB
17Hibás válasz50ms26680 KiB
subtask50/25
18Hibás válasz104ms34092 KiB
19Hibás válasz109ms36864 KiB
20Hibás válasz104ms41144 KiB
21Hibás válasz101ms42444 KiB
22Hibás válasz104ms46948 KiB