52682023-04-24 21:42:56k_balintTurista járatokcpp14Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva12ms21284 KiB
2Elfogadva17ms23408 KiB
subtask210/10
3Elfogadva10ms21824 KiB
4Elfogadva9ms22032 KiB
5Elfogadva10ms22248 KiB
6Elfogadva10ms22088 KiB
7Elfogadva10ms22356 KiB
subtask310/10
8Elfogadva10ms22300 KiB
9Elfogadva9ms22560 KiB
10Elfogadva10ms22884 KiB
11Elfogadva10ms23112 KiB
12Elfogadva14ms24660 KiB
subtask410/10
13Elfogadva18ms26164 KiB
14Elfogadva10ms23048 KiB
15Elfogadva12ms23152 KiB
16Elfogadva13ms23228 KiB
17Elfogadva141ms64480 KiB
18Elfogadva48ms31576 KiB
19Elfogadva64ms34348 KiB
20Elfogadva52ms32092 KiB
subtask510/10
21Elfogadva17ms25708 KiB
22Elfogadva9ms23836 KiB
23Elfogadva9ms23944 KiB
24Elfogadva9ms24172 KiB
25Elfogadva93ms48104 KiB
26Elfogadva16ms25392 KiB
27Elfogadva14ms25648 KiB
subtask660/60
28Elfogadva9ms24072 KiB
29Elfogadva9ms24252 KiB
30Elfogadva10ms24448 KiB
31Elfogadva10ms24468 KiB
32Elfogadva12ms24856 KiB
33Elfogadva13ms25160 KiB
34Elfogadva16ms26008 KiB
35Elfogadva16ms26060 KiB
36Elfogadva16ms26000 KiB
37Elfogadva141ms65580 KiB
38Elfogadva52ms32324 KiB
39Elfogadva50ms32464 KiB
40Elfogadva48ms32456 KiB
41Elfogadva48ms32492 KiB
42Elfogadva48ms32480 KiB
43Elfogadva48ms32448 KiB
44Elfogadva48ms32460 KiB
45Elfogadva63ms35260 KiB
46Elfogadva48ms32516 KiB
47Elfogadva48ms32536 KiB
48Elfogadva52ms32352 KiB
49Elfogadva50ms32584 KiB
50Elfogadva48ms32544 KiB