src/test/aoj_GRL_3_B.cpp

View this file on GitHub
Last update: 2026-03-17 19:58:42+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include "../graph/lowlink.hpp"

int main(){
    int N,M;
    cin>>N>>M;
    vector<vector<int>> G(N);
    rep(i,M){
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    rep(i,N)sort(all(G[i]));
    LowLink LL(G);
    rep(i,N)for(int j: G[i])if(i<j){
        if(LL.is_bridge(i,j)){
            cout<<i<<" "<<j<<"\n";
        }
    }
}

#line 1 "src/test/aoj_GRL_3_B.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/graph/lowlink.hpp"

struct LowLink{
    vector<vector<int>> G;
    vector<int> ord,low,vis,isa;    
    int dfs(int v, int p, int t){
        vis[v]=1;
        ord[v]=t++;
        low[v]=ord[v];
        int cnt=0;
        for(int e: G[v]){
            if(!vis[e]){
                cnt++;
                t=dfs(e,v,t);
                chmin(low[v], low[e]);
                if(~p&&ord[v]<=low[e])isa[v]=1;
                if(p==-1&&cnt==2)isa[v]=1;
            }
            else if(e!=p){
                chmin(low[v],ord[e]);
            }
        }
        return t;
    }
    
    LowLink(vector<vector<int>> G): G(G) {
        int N=si(G);
        ord.assign(N,0);
        low.assign(N,0);
        vis.assign(N,0);
        isa.assign(N,0);
        int t=0;
        rep(i,si(G)){
            if(!vis[i]){
                t=dfs(i,-1,t);
            }
        }
    }
    bool is_bridge(int u, int v){
        if(ord[u]>ord[v])swap(u,v);
        return ord[u]<low[v];
    }
};
#line 3 "src/test/aoj_GRL_3_B.cpp"

int main(){
    int N,M;
    cin>>N>>M;
    vector<vector<int>> G(N);
    rep(i,M){
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    rep(i,N)sort(all(G[i]));
    LowLink LL(G);
    rep(i,N)for(int j: G[i])if(i<j){
        if(LL.is_bridge(i,j)){
            cout<<i<<" "<<j<<"\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	5 ms	4 MB
g++	00_small_01.in	AC	5 ms	4 MB
g++	00_small_02.in	AC	5 ms	4 MB
g++	00_small_03.in	AC	5 ms	4 MB
g++	00_small_04.in	AC	5 ms	3 MB
g++	00_small_05.in	AC	5 ms	4 MB
g++	01_critical_00.in	AC	5 ms	3 MB
g++	01_critical_01.in	AC	5 ms	4 MB
g++	01_critical_02.in	AC	5 ms	4 MB
g++	01_critical_03.in	AC	5 ms	4 MB
g++	01_critical_04.in	AC	5 ms	4 MB
g++	01_critical_05.in	AC	5 ms	4 MB
g++	01_critical_06.in	AC	5 ms	4 MB
g++	01_critical_07.in	AC	5 ms	4 MB
g++	01_critical_08.in	AC	5 ms	4 MB
g++	01_critical_09.in	AC	5 ms	4 MB
g++	01_critical_10.in	AC	5 ms	4 MB
g++	01_critical_11.in	AC	5 ms	4 MB
g++	01_critical_12.in	AC	5 ms	4 MB
g++	02_grid_00.in	AC	5 ms	4 MB
g++	02_grid_01.in	AC	5 ms	4 MB
g++	02_grid_02.in	AC	5 ms	4 MB
g++	03_rand_00.in	AC	5 ms	4 MB
g++	03_rand_01.in	AC	5 ms	4 MB
g++	03_rand_02.in	AC	5 ms	4 MB
g++	03_rand_03.in	AC	5 ms	4 MB
g++	03_rand_04.in	AC	5 ms	4 MB
g++	03_rand_05.in	AC	5 ms	4 MB
g++	03_rand_06.in	AC	5 ms	4 MB
g++	03_rand_07.in	AC	5 ms	4 MB
g++	03_rand_08.in	AC	6 ms	4 MB
g++	03_rand_09.in	AC	7 ms	4 MB
g++	03_rand_10.in	AC	7 ms	4 MB
g++	03_rand_11.in	AC	9 ms	4 MB
g++	04_linear_00.in	AC	6 ms	4 MB
g++	04_linear_01.in	AC	7 ms	4 MB
g++	04_linear_02.in	AC	15 ms	6 MB
g++	04_linear_03.in	AC	16 ms	6 MB
g++	05_maximum_00.in	AC	25 ms	6 MB
g++	05_maximum_01.in	AC	30 ms	7 MB