12402022-03-28 16:21:49k_balintTurista járatokcpp14Accepted 100/100181ms78188 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=40004;

struct edge{
    int v,id;
    edge(int vv, int i){
        v=vv; id=i;
    }
    edge(){
        v=id=0;
    }
};

int n,m,k;
vector<edge> adj[c];
int t[c],l[c];
bool used[10*c];
stack<int> s;
int tt; int cnt;
vector<int> comp[3*c];
int cut[c];
int ecmp[10*c];
bool good[3*c];
bool cut_cmp[3*c];

void new_comp(int id){
    while(!s.empty() && s.top() != id){
        int cur=s.top();
        s.pop();
        if(cur<=k) good[cnt]=1;
        ecmp[cur]=cnt;
        comp[cnt].push_back(cur);
    }

    if(!s.empty()){
        int cur=s.top();
        s.pop();
        if(cur<=k) good[cnt]=1;
        ecmp[cur]=cnt;
        comp[cnt].push_back(cur);
    }

    ++cnt;
}

vector<int> tree[3*c];
vector<edge> edges;

void dfs(int v, int p){
    t[v]=l[v]=tt++;
    bool children=0;

    for(edge x:adj[v]){
        if(x.id==p) continue;
        if(!used[x.id]){
            used[x.id]=1;
            s.push(x.id);
        }

        if(!t[x.v]){
            dfs(x.v,x.id);
            l[v]=min(l[v],l[x.v]);

            if(v==1?children:l[x.v]>=t[v]){
                if(!cut[v]){
                    cut_cmp[cnt]=1;
                    cut[v]=cnt;
                    comp[cnt].push_back(v); ++cnt;
                }
                tree[cut[v]].push_back(cnt);
                tree[cnt].push_back(cut[v]);
                new_comp(x.id);
            }

            children=1;
        }
        else l[v]=min(l[v],t[x.v]);
    }

    if(cut[v] && p!=0){
        edges.push_back(edge(cut[v],p));
    }

    if(v==1 && !s.empty()){
        if(cut[v]){
            tree[cut[v]].push_back(cnt);
            tree[cnt].push_back(cut[v]);
        }
        new_comp(-1);
    }
}

bool vis[3*c];
void dfs2(int v, bool g){
    vis[v]=1; good[v]|=g;
    for(int x:tree[v]){
        if(!vis[x]){
            dfs2(x,good[v]);
        }
    }
}

bool ans[c];
edge edg[10*c];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int a,b; cin>>a>>b;
        edg[i]=edge(a,b);
        adj[a].push_back(edge(b,i));
        adj[b].push_back(edge(a,i));
    }

    tt=1; cnt=1;
    dfs(1,0);

    for(edge x:edges){
        tree[x.v].push_back(ecmp[x.id]);
        tree[ecmp[x.id]].push_back(x.v);
    }

    if(adj[1].empty()){
        cout << 0 << endl;
        return 0;
    }

    if(!cut[1]) dfs2(ecmp[adj[1][0].id],0);
    else dfs2(cut[1],0);

    for(int i=1;i<cnt;i++){
        if(!good[i]) continue;
        if(cut_cmp[i]){
            ans[comp[i][0]]=1;
            continue;
        }

        for(int x:comp[i]){
            int a=edg[x].v;
            int b=edg[x].id;
            if(!cut[a]) ans[a]=1;
            if(!cut[b]) ans[b]=1;
        }
    }

    ans[1]=0;

    int ans2=0;
    for(int i=1;i<=n;i++){
        if(ans[i]) ++ans2;
    }

    cout << ans2 << '\n';

    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout << i << ' ';
        }
    }

    cout << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted12ms21256 KiB
2Accepted19ms23268 KiB
subtask210/10
3Accepted10ms21460 KiB
4Accepted10ms21472 KiB
5Accepted9ms21468 KiB
6Accepted12ms21476 KiB
7Accepted10ms21488 KiB
subtask310/10
8Accepted9ms21484 KiB
9Accepted9ms21488 KiB
10Accepted9ms21508 KiB
11Accepted10ms21784 KiB
12Accepted14ms23212 KiB
subtask410/10
13Accepted17ms24816 KiB
14Accepted9ms21656 KiB
15Accepted10ms21876 KiB
16Accepted10ms21960 KiB
17Accepted181ms67036 KiB
18Accepted59ms34904 KiB
19Accepted76ms38908 KiB
20Accepted56ms37216 KiB
subtask510/10
21Accepted17ms30780 KiB
22Accepted10ms29044 KiB
23Accepted12ms29068 KiB
24Accepted12ms29220 KiB
25Accepted115ms56260 KiB
26Accepted17ms33576 KiB
27Accepted17ms33724 KiB
subtask660/60
28Accepted10ms32372 KiB
29Accepted10ms32408 KiB
30Accepted12ms32640 KiB
31Accepted13ms32756 KiB
32Accepted13ms33008 KiB
33Accepted17ms33288 KiB
34Accepted17ms34332 KiB
35Accepted17ms34484 KiB
36Accepted17ms34632 KiB
37Accepted181ms78188 KiB
38Accepted54ms45908 KiB
39Accepted54ms46960 KiB
40Accepted56ms47844 KiB
41Accepted57ms48768 KiB
42Accepted54ms49500 KiB
43Accepted57ms50452 KiB
44Accepted56ms51448 KiB
45Accepted83ms55568 KiB
46Accepted59ms53724 KiB
47Accepted57ms54656 KiB
48Accepted59ms55344 KiB
49Accepted57ms56380 KiB
50Accepted65ms57264 KiB