Submission #478327

#	Time	Username	Problem	Language	Result	Execution time	Memory
478327		hjc4vr	Pipes (CEOI15_pipes)	C++14	0 / 100	1219 ms	65540 KiB

pipes

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> adj[100005];
vector<pair<int,int>> ans;
int low[100005],depths[100005];
 
void dfs(int cur,int par){
    depths[cur] = depths[par] + 1;
    low[cur] = depths[cur];
//    cout << 1;
    for (auto it : adj[cur]){
        if (it!=par){
            if (depths[it]==-1){
                dfs(it,cur);
                low[cur] = min(low[cur],low[it]);
                if (low[it]>depths[cur]){
                    ans.push_back(make_pair(it,cur));
                }
                
            }else{
                low[cur] = min(low[cur],depths[it]);
            }
        }
    }
}
 
 
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    fill(depths,depths+100005,-1);
//    cout << depths[1];
    for (int i=0;i<m;++i){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i=1;i<=n;++i){
        if (depths[i]==-1)dfs(i,i);
    }
    for (auto it:ans){
        int a = it.first, b= it.second;
        if (a<b) swap(a,b);
        cout << b  << " " << a << '\n';
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10