UVa 610 Street Directions

Uva 610 Street Directions
http://uva.onlinejudge.org/external/6/610.html

問題概要

無向グラフがあたえられる。
いくつかのエッジを有向辺に変更する。
変更後もすべて強連結なグラフでないといけない。
選ぶエッジを最大化したとき、得られる有向グラフを構成するエッジを答えよ。

解法

橋をみつけ、橋だけ無向辺のままにする。
分割した橋の持たないグラフにエッジをDFSで割り振る。
橋を含まないグラフでDFS木を作ると、
根以外のノードsは必ずsの祖先への後退辺をs自身、あるいは、sの子孫が持つ。
よって、

• 全ての子ノードは根ノードへの道を持つ
• 根ノードは子ノードへの道を持つ

ので、木を構成している辺と後退辺で構成すると、強連結なグラフになる。

ソース

#include<iostream>
#include<algorithm>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int V = 1000;
int n;
bool edge[V][V], preUsed[V][V], used[V][V];
int preNum[V], low[V], rootNode, defultID[V];
vector<pair<int, int> > Edge;

int dfs(int nowNode, int &nowNum){
  low[nowNode] = preNum[nowNode] = nowNum;
  defultID[nowNum] = nowNode;
  nowNum++;
  rep(i, n){
    if(!edge[nowNode][i])continue;
    if(preNum[i] >= 0){
      if(preUsed[i][nowNode])continue;
      low[nowNode] = min(low[nowNode], preNum[i]);
      if(used[nowNode][i])continue;
      Edge.push_back(make_pair(nowNode, i));
      used[nowNode][i] = used[i][nowNode] = true;
    }
    else{
      preUsed[nowNode][i] = true;
      Edge.push_back(make_pair(nowNode, i));
      used[nowNode][i] = used[i][nowNode] = true;
      low[nowNode] = min(dfs(i, nowNum), low[nowNode]);
    }
  }
  return low[nowNode]; 
}
void getBridge(){
  rep(i, n){
    rep(j, n){
      if(!preUsed[i][j])continue;
      if(low[j] == preNum[j]){
        Edge.push_back(make_pair(defultID[max(preNum[i], preNum[j])], defultID[min(preNum[i], preNum[j])]));
      }
    }
  }
}
void setGraph(){
  rootNode = 0;
  rep(i, n){
    preNum[i] = -1;
    rep(j, n){
      used[i][j] = false;
      preUsed[i][j] = false;
    }
  }
  int id= 0;
  dfs(rootNode, id);
}

int main(){
  int m;
  int tc = 0;
  while(cin >> n >> m){
    tc++;
    if(n == 0&& m == 0)break;
    cout << tc << endl << endl;
    rep(i, n)rep(j, n)edge[i][j] = false;
    rep(i, m){
      int from, to;
      cin >> from >> to;
      from--;to--;
      edge[from][to] = edge[to][from] = true;
    }
    Edge.clear();
    setGraph();
    getBridge();
    FOR(it, Edge){
      cout << it->first + 1 <<' ' << it->second +1<< endl;
    }
    cout << "#" << endl;
  }
  return 0;
}