52682023-04-24 21:42:56k_balintTurista járatokcpp14Accepted 100/100141ms65580 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
1Accepted12ms21284 KiB
2Accepted17ms23408 KiB
subtask210/10
3Accepted10ms21824 KiB
4Accepted9ms22032 KiB
5Accepted10ms22248 KiB
6Accepted10ms22088 KiB
7Accepted10ms22356 KiB
subtask310/10
8Accepted10ms22300 KiB
9Accepted9ms22560 KiB
10Accepted10ms22884 KiB
11Accepted10ms23112 KiB
12Accepted14ms24660 KiB
subtask410/10
13Accepted18ms26164 KiB
14Accepted10ms23048 KiB
15Accepted12ms23152 KiB
16Accepted13ms23228 KiB
17Accepted141ms64480 KiB
18Accepted48ms31576 KiB
19Accepted64ms34348 KiB
20Accepted52ms32092 KiB
subtask510/10
21Accepted17ms25708 KiB
22Accepted9ms23836 KiB
23Accepted9ms23944 KiB
24Accepted9ms24172 KiB
25Accepted93ms48104 KiB
26Accepted16ms25392 KiB
27Accepted14ms25648 KiB
subtask660/60
28Accepted9ms24072 KiB
29Accepted9ms24252 KiB
30Accepted10ms24448 KiB
31Accepted10ms24468 KiB
32Accepted12ms24856 KiB
33Accepted13ms25160 KiB
34Accepted16ms26008 KiB
35Accepted16ms26060 KiB
36Accepted16ms26000 KiB
37Accepted141ms65580 KiB
38Accepted52ms32324 KiB
39Accepted50ms32464 KiB
40Accepted48ms32456 KiB
41Accepted48ms32492 KiB
42Accepted48ms32480 KiB
43Accepted48ms32448 KiB
44Accepted48ms32460 KiB
45Accepted63ms35260 KiB
46Accepted48ms32516 KiB
47Accepted48ms32536 KiB
48Accepted52ms32352 KiB
49Accepted50ms32584 KiB
50Accepted48ms32544 KiB