橋と関節点 (from AOJ: GRL_3-A Discussion Solution Statistics Submit Connected Components - Articulation Points, GRL_3-B Discussion Solution Statistics Submit Connected Components - Bridges)

GRL_3_A.cpp

// AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1852309)
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 10000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
typedef pair<P, int> PI;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

// 関節点を求める
// 以下を参考にさせていただきました
// http://kagamiz.hatenablog.com/entry/2013/10/05/005213
#define V 100000

int v, e;
vector<int> g[V];
// ord[i]: 頂点iのDFS木の到達番号(0 => DFSにて未到達)
// low[i]: 頂点iから後退辺を一回通って到達し得る頂点vのord[v]のうち最小のもの
int ord[V], low[V];
int cnt;
vector<int> ans;

int dfs(int v, int f) {
  ord[v] = ++cnt;
  int res = cnt;  // 実質low[v]
  bool a = false; // 関節点(Articulation Points)かどうか
  int d = 0;
  rep(i, g[v].size()) {
    int t = g[v][i];
    if(v == t) continue;
    if(!ord[t]) {
      // 頂点tが未到達 => tを再帰的に探索し、low[t]の値をチェック
      ++d;
      int r = dfs(t, v);
      // 頂点vが根以外で、ord[v] <= low[t]だった場合、vは関節点
      if(f != -1 && ord[v] <= r) {
        a = true;
      }
      res = mind(res, r);
    } else {
      // 頂点tが到達済み => ord[t]の値が最小値であれば、low[v] <- ord[t]
      res = mind(res, ord[t]);
    }
  }
  low[v] = res;
  // 頂点vが根で、DFS木における次数が1より大きい場合、それは関節点
  if(f == -1 && d > 1) ans.push_back(v);
  if(a) {
    ans.push_back(v);
  }
  return res;
}

int main() {
  cin >> v >> e;
  rep(i, e) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  dfs(0, -1);
  sort(ALL(ans));
  rep(i, ans.size()) {
    cout << ans[i] << endl;
  }
  return 0;
}

GRL_3_B.cpp

// AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1852088)
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 10000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
typedef pair<P, int> PI;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

// 橋を求める
#define V 100000

int v, e;
vector<int> g[V];
vector<P> ans;
bool used[V], fin[V];
int memo[V];

int dfs(int v, int f) {
  int cnt = 0;
  used[v] = true;
  rep(i, g[v].size()) {
    int t = g[v][i];
    if(used[t]) {
      // 到達済み => 後退辺
      // 頂点vで+1して、後退辺の先の頂点で-1する
      if(t != f && !fin[t]) {
        cnt += 1;
        memo[t] += 1;
      }
    } else {
      // 未到達 => 再帰的に探索 => 橋であるかを判定
      int res = dfs(t, v);
      // res=0 => 頂点vの親となる頂点へ到達し得る後退辺を持たない
      if(res == 0) {
        // (v, t)は橋
        ans.push_back(v < t ? P(v, t) : P(t, v));
      }
      cnt += res;
    }
  }
  cnt -= memo[v];
  fin[v] = true;
  return cnt;
}

int main() {
  cin >> v >> e;
  rep(i, e) {
    int s, t;
    cin >> s >> t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  dfs(0, -1);
  sort(ALL(ans));
  rep(i, ans.size()) {
    P &e = ans[i];
    cout << e.first << " " << e.second << endl;
  }
  return 0;
}