52672023-04-24 21:41:40k_balintTurista járatokcpp14Wrong answer 10/100136ms51764 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=40005;

int n,m,k,tt;
int id;
vector<pair<int,int>> adj[c];
int t[c],l[c],vag[c],comp[10*c];
bool volt[10*c];
bool dp[c];
pair<int,int> el[10*c];

stack<int> st;
vector<int> tree[c];

void dfs(int v, int p){
    ++tt;
    t[v]=l[v]=tt;
    int db=0;
    for(pair<int,int> x:adj[v]){
        if(x.first==p) continue;
        if(!volt[x.second]) {st.push(x.second); volt[x.second]=1;}
        if(!t[x.first]){
            ++db;
            dfs(x.first,v);
            l[v]=min(l[v],l[x.first]);
            if(p!=0 && l[x.first]>=t[v]){
                if(vag[v]==0){++id; vag[v]=id;}
                ++id;
                while(st.top()!=x.second){
                    int cur=st.top(); st.pop();
                    comp[cur]=id;
                }
                comp[st.top()]=id;
                st.pop();
            }
            else if(p==0){
                if(db==2){++id; vag[v]=id;}
                ++id;
                while(!st.empty()){
                    int cur=st.top(); st.pop();
                    comp[cur]=id;
                }
            }
        }
        else l[v]=min(l[v],t[x.first]);
    }
}

bool vis[c];
void dfs2(int v, int p){
    if(dp[p]) dp[v]=1;
    vis[v]=1;
    for(int x:tree[v]){
        if(!vis[x]) dfs2(x,v);
    }
}

bool ans[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;
        el[i]=make_pair(a,b);
        adj[a].push_back(make_pair(b,i));
        adj[b].push_back(make_pair(a,i));
    }

    tt=0,id=0;
    dfs(1,0);

    int z=0;
    for(int i=1;i<=m;i++){
        int a=el[i].first,b=el[i].second;
        int cm=comp[i];
        if(a==1 || b==1) z=cm;
        if(i<=k) dp[cm]=1;
        if(vag[a]!=0){
            tree[vag[a]].push_back(cm);
            tree[cm].push_back(vag[b]);
        }
        if(vag[b]!=0){
            tree[vag[b]].push_back(cm);
            tree[cm].push_back(vag[b]);
        }
    }

    if(vag[1]!=0) dfs2(vag[1],0);
    else dfs2(z,0);


    ans[1]=0;
    for(int i=2;i<=m;i++){
        if(dp[comp[i]]) {
            if(vag[el[i].first]==0) ans[el[i].first]=1;
            if(vag[el[i].second]==0) ans[el[i].second]=1;
        }
    }

    int cnt=0;
    for(int i=2;i<=n;i++){
        if(vag[i]!=0 && dp[vag[i]]) ans[i]=1;
        if(ans[i]) ++cnt;
    }    

    cout << cnt << endl;
    for(int i=1;i<=m;i++){
        if(ans[i]) cout<<i << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms5668 KiB
2Accepted10ms7824 KiB
subtask20/10
3Wrong answer4ms6068 KiB
4Wrong answer4ms6284 KiB
5Accepted4ms6492 KiB
6Accepted4ms6708 KiB
7Wrong answer4ms7056 KiB
subtask30/10
8Accepted4ms7268 KiB
9Wrong answer4ms7468 KiB
10Wrong answer4ms7432 KiB
11Wrong answer4ms7876 KiB
12Wrong answer7ms8788 KiB
subtask40/10
13Wrong answer8ms9996 KiB
14Accepted4ms7908 KiB
15Accepted4ms8304 KiB
16Accepted4ms8472 KiB
17Accepted127ms51160 KiB
18Accepted41ms16740 KiB
19Wrong answer59ms20036 KiB
20Wrong answer43ms16984 KiB
subtask510/10
21Accepted9ms10096 KiB
22Accepted4ms8336 KiB
23Accepted4ms8648 KiB
24Accepted4ms8532 KiB
25Accepted82ms33468 KiB
26Accepted9ms9980 KiB
27Accepted9ms9928 KiB
subtask60/60
28Accepted4ms8500 KiB
29Accepted4ms8780 KiB
30Accepted6ms9204 KiB
31Accepted6ms9332 KiB
32Accepted7ms9604 KiB
33Accepted7ms9760 KiB
34Accepted10ms10728 KiB
35Accepted10ms10720 KiB
36Accepted9ms10608 KiB
37Accepted136ms51764 KiB
38Accepted43ms17300 KiB
39Accepted43ms17316 KiB
40Accepted41ms17272 KiB
41Wrong answer41ms17316 KiB
42Wrong answer41ms17332 KiB
43Accepted43ms17276 KiB
44Wrong answer41ms17404 KiB
45Accepted56ms20532 KiB
46Wrong answer41ms17324 KiB
47Wrong answer41ms17336 KiB
48Accepted41ms17200 KiB
49Accepted41ms17396 KiB
50Accepted43ms17332 KiB