5268 2023. 04. 24 21:42:56 k_balint Turista járatok cpp14 Elfogadva 100/100 141ms 65580 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 12ms 21284 KiB
2 Elfogadva 17ms 23408 KiB
subtask2 10/10
3 Elfogadva 10ms 21824 KiB
4 Elfogadva 9ms 22032 KiB
5 Elfogadva 10ms 22248 KiB
6 Elfogadva 10ms 22088 KiB
7 Elfogadva 10ms 22356 KiB
subtask3 10/10
8 Elfogadva 10ms 22300 KiB
9 Elfogadva 9ms 22560 KiB
10 Elfogadva 10ms 22884 KiB
11 Elfogadva 10ms 23112 KiB
12 Elfogadva 14ms 24660 KiB
subtask4 10/10
13 Elfogadva 18ms 26164 KiB
14 Elfogadva 10ms 23048 KiB
15 Elfogadva 12ms 23152 KiB
16 Elfogadva 13ms 23228 KiB
17 Elfogadva 141ms 64480 KiB
18 Elfogadva 48ms 31576 KiB
19 Elfogadva 64ms 34348 KiB
20 Elfogadva 52ms 32092 KiB
subtask5 10/10
21 Elfogadva 17ms 25708 KiB
22 Elfogadva 9ms 23836 KiB
23 Elfogadva 9ms 23944 KiB
24 Elfogadva 9ms 24172 KiB
25 Elfogadva 93ms 48104 KiB
26 Elfogadva 16ms 25392 KiB
27 Elfogadva 14ms 25648 KiB
subtask6 60/60
28 Elfogadva 9ms 24072 KiB
29 Elfogadva 9ms 24252 KiB
30 Elfogadva 10ms 24448 KiB
31 Elfogadva 10ms 24468 KiB
32 Elfogadva 12ms 24856 KiB
33 Elfogadva 13ms 25160 KiB
34 Elfogadva 16ms 26008 KiB
35 Elfogadva 16ms 26060 KiB
36 Elfogadva 16ms 26000 KiB
37 Elfogadva 141ms 65580 KiB
38 Elfogadva 52ms 32324 KiB
39 Elfogadva 50ms 32464 KiB
40 Elfogadva 48ms 32456 KiB
41 Elfogadva 48ms 32492 KiB
42 Elfogadva 48ms 32480 KiB
43 Elfogadva 48ms 32448 KiB
44 Elfogadva 48ms 32460 KiB
45 Elfogadva 63ms 35260 KiB
46 Elfogadva 48ms 32516 KiB
47 Elfogadva 48ms 32536 KiB
48 Elfogadva 52ms 32352 KiB
49 Elfogadva 50ms 32584 KiB
50 Elfogadva 48ms 32544 KiB