12402022-03-28 16:21:49k_balintTurista járatokcpp14Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms21256 KiB
2Elfogadva19ms23268 KiB
subtask210/10
3Elfogadva10ms21460 KiB
4Elfogadva10ms21472 KiB
5Elfogadva9ms21468 KiB
6Elfogadva12ms21476 KiB
7Elfogadva10ms21488 KiB
subtask310/10
8Elfogadva9ms21484 KiB
9Elfogadva9ms21488 KiB
10Elfogadva9ms21508 KiB
11Elfogadva10ms21784 KiB
12Elfogadva14ms23212 KiB
subtask410/10
13Elfogadva17ms24816 KiB
14Elfogadva9ms21656 KiB
15Elfogadva10ms21876 KiB
16Elfogadva10ms21960 KiB
17Elfogadva181ms67036 KiB
18Elfogadva59ms34904 KiB
19Elfogadva76ms38908 KiB
20Elfogadva56ms37216 KiB
subtask510/10
21Elfogadva17ms30780 KiB
22Elfogadva10ms29044 KiB
23Elfogadva12ms29068 KiB
24Elfogadva12ms29220 KiB
25Elfogadva115ms56260 KiB
26Elfogadva17ms33576 KiB
27Elfogadva17ms33724 KiB
subtask660/60
28Elfogadva10ms32372 KiB
29Elfogadva10ms32408 KiB
30Elfogadva12ms32640 KiB
31Elfogadva13ms32756 KiB
32Elfogadva13ms33008 KiB
33Elfogadva17ms33288 KiB
34Elfogadva17ms34332 KiB
35Elfogadva17ms34484 KiB
36Elfogadva17ms34632 KiB
37Elfogadva181ms78188 KiB
38Elfogadva54ms45908 KiB
39Elfogadva54ms46960 KiB
40Elfogadva56ms47844 KiB
41Elfogadva57ms48768 KiB
42Elfogadva54ms49500 KiB
43Elfogadva57ms50452 KiB
44Elfogadva56ms51448 KiB
45Elfogadva83ms55568 KiB
46Elfogadva59ms53724 KiB
47Elfogadva57ms54656 KiB
48Elfogadva59ms55344 KiB
49Elfogadva57ms56380 KiB
50Elfogadva65ms57264 KiB