12392022-03-28 16:17:12k_balintTurista járatokcpp14Runtime error 20/100136ms53616 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[4*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
1Accepted9ms17516 KiB
2Accepted17ms19512 KiB
subtask210/10
3Accepted8ms17668 KiB
4Accepted8ms17680 KiB
5Accepted8ms17684 KiB
6Accepted8ms17684 KiB
7Accepted10ms17696 KiB
subtask310/10
8Accepted9ms17692 KiB
9Accepted8ms17692 KiB
10Accepted8ms17708 KiB
11Accepted12ms18124 KiB
12Accepted13ms19424 KiB
subtask40/10
13Accepted16ms21164 KiB
14Accepted8ms17868 KiB
15Accepted8ms18092 KiB
16Accepted9ms18292 KiB
17Runtime error133ms42468 KiB
18Accepted52ms31116 KiB
19Accepted78ms35172 KiB
20Accepted59ms33548 KiB
subtask50/10
21Accepted14ms26992 KiB
22Accepted10ms25392 KiB
23Accepted8ms25416 KiB
24Accepted8ms25440 KiB
25Runtime error97ms43328 KiB
26Accepted17ms29936 KiB
27Accepted16ms30064 KiB
subtask60/60
28Accepted8ms28592 KiB
29Accepted9ms28624 KiB
30Accepted10ms28844 KiB
31Accepted12ms29084 KiB
32Accepted10ms29212 KiB
33Accepted12ms29504 KiB
34Accepted17ms30540 KiB
35Accepted17ms30680 KiB
36Accepted16ms30836 KiB
37Runtime error136ms53616 KiB
38Accepted54ms42156 KiB
39Accepted56ms43168 KiB
40Accepted54ms44076 KiB
41Accepted57ms44972 KiB
42Accepted54ms45824 KiB
43Accepted57ms46732 KiB
44Accepted52ms47652 KiB
45Accepted82ms51824 KiB
46Accepted57ms50060 KiB
47Accepted56ms50984 KiB
48Accepted61ms51632 KiB
49Accepted54ms52596 KiB
50Accepted54ms53460 KiB