12392022-03-28 16:17:12k_balintTurista járatokcpp14Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva9ms17516 KiB
2Elfogadva17ms19512 KiB
subtask210/10
3Elfogadva8ms17668 KiB
4Elfogadva8ms17680 KiB
5Elfogadva8ms17684 KiB
6Elfogadva8ms17684 KiB
7Elfogadva10ms17696 KiB
subtask310/10
8Elfogadva9ms17692 KiB
9Elfogadva8ms17692 KiB
10Elfogadva8ms17708 KiB
11Elfogadva12ms18124 KiB
12Elfogadva13ms19424 KiB
subtask40/10
13Elfogadva16ms21164 KiB
14Elfogadva8ms17868 KiB
15Elfogadva8ms18092 KiB
16Elfogadva9ms18292 KiB
17Futási hiba133ms42468 KiB
18Elfogadva52ms31116 KiB
19Elfogadva78ms35172 KiB
20Elfogadva59ms33548 KiB
subtask50/10
21Elfogadva14ms26992 KiB
22Elfogadva10ms25392 KiB
23Elfogadva8ms25416 KiB
24Elfogadva8ms25440 KiB
25Futási hiba97ms43328 KiB
26Elfogadva17ms29936 KiB
27Elfogadva16ms30064 KiB
subtask60/60
28Elfogadva8ms28592 KiB
29Elfogadva9ms28624 KiB
30Elfogadva10ms28844 KiB
31Elfogadva12ms29084 KiB
32Elfogadva10ms29212 KiB
33Elfogadva12ms29504 KiB
34Elfogadva17ms30540 KiB
35Elfogadva17ms30680 KiB
36Elfogadva16ms30836 KiB
37Futási hiba136ms53616 KiB
38Elfogadva54ms42156 KiB
39Elfogadva56ms43168 KiB
40Elfogadva54ms44076 KiB
41Elfogadva57ms44972 KiB
42Elfogadva54ms45824 KiB
43Elfogadva57ms46732 KiB
44Elfogadva52ms47652 KiB
45Elfogadva82ms51824 KiB
46Elfogadva57ms50060 KiB
47Elfogadva56ms50984 KiB
48Elfogadva61ms51632 KiB
49Elfogadva54ms52596 KiB
50Elfogadva54ms53460 KiB