Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-11

SRM184 div2 (過去問)

00:15

Hard - TeamBuilder

グラフが与えられるので、他の全てのノードへ行けるノードの数と、他の全てのノードから入って来れるノードの数を求める。

Floyd-Warshallを使って、ノードのつながりを調べます。最小コストを求める訳ではないので、つながっているパスには単に1を入れていきます。また、自分から自分へのパスに1を設定するのがポイントです。

今回の問題は、tutorialでFloyd-Warshallの例題として出されていたものなので、このアルゴリズムを使う事ができたんですが、このヒントなくこの問題に取り組んでいたら、もっと力づくで長くなるコードを書いてしまって、バグを埋め込んだりして時間がかかってしまいそうです。

追記

tutorialをよく読んでみると、ワーシャルフロイドはグラフの接続性を調べるのにもよく使われるようです。推移閉包問題と呼ばれるそうです。

There are other uses for Floyd-Warshall as well; it can be used to find connectivity in a graph (known as the Transitive Closure of a graph). 

見落としていました。

class TeamBuilder {
public:
  vector <int> specialLocations(vector <string> paths)
  {
    vector <int> ret(2, 0);

    for (int i=0; i<paths.size(); i++)
      paths[i][i] = '1';

    for (int k=0; k<paths.size(); k++)
      for (int i=0; i<paths.size(); i++)
	for (int j=0; j<paths.size(); j++)
	  if (paths[i][k] == '1' && paths[k][j] == '1')
	    paths[i][j] = '1';

    for (int i=0; i<paths.size(); i++)
      {
	int row = 0, col = 0;
	for (int j=0; j<paths.size(); j++)
	  {
	    if (paths[i][j] == '1')
	      row++;
	    if (paths[j][i] == '1')
	      col++;
	  }
 
	if (row == paths.size())
	  ret[0]++;
	if (col == paths.size())
	  ret[1]++;
      }

    return ret;
  }
};