52672023-04-24 21:41:40k_balintTurista járatokcpp14Hibás válasz 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 << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms5668 KiB
2Elfogadva10ms7824 KiB
subtask20/10
3Hibás válasz4ms6068 KiB
4Hibás válasz4ms6284 KiB
5Elfogadva4ms6492 KiB
6Elfogadva4ms6708 KiB
7Hibás válasz4ms7056 KiB
subtask30/10
8Elfogadva4ms7268 KiB
9Hibás válasz4ms7468 KiB
10Hibás válasz4ms7432 KiB
11Hibás válasz4ms7876 KiB
12Hibás válasz7ms8788 KiB
subtask40/10
13Hibás válasz8ms9996 KiB
14Elfogadva4ms7908 KiB
15Elfogadva4ms8304 KiB
16Elfogadva4ms8472 KiB
17Elfogadva127ms51160 KiB
18Elfogadva41ms16740 KiB
19Hibás válasz59ms20036 KiB
20Hibás válasz43ms16984 KiB
subtask510/10
21Elfogadva9ms10096 KiB
22Elfogadva4ms8336 KiB
23Elfogadva4ms8648 KiB
24Elfogadva4ms8532 KiB
25Elfogadva82ms33468 KiB
26Elfogadva9ms9980 KiB
27Elfogadva9ms9928 KiB
subtask60/60
28Elfogadva4ms8500 KiB
29Elfogadva4ms8780 KiB
30Elfogadva6ms9204 KiB
31Elfogadva6ms9332 KiB
32Elfogadva7ms9604 KiB
33Elfogadva7ms9760 KiB
34Elfogadva10ms10728 KiB
35Elfogadva10ms10720 KiB
36Elfogadva9ms10608 KiB
37Elfogadva136ms51764 KiB
38Elfogadva43ms17300 KiB
39Elfogadva43ms17316 KiB
40Elfogadva41ms17272 KiB
41Hibás válasz41ms17316 KiB
42Hibás válasz41ms17332 KiB
43Elfogadva43ms17276 KiB
44Hibás válasz41ms17404 KiB
45Elfogadva56ms20532 KiB
46Hibás válasz41ms17324 KiB
47Hibás válasz41ms17336 KiB
48Elfogadva41ms17200 KiB
49Elfogadva41ms17396 KiB
50Elfogadva43ms17332 KiB