Checking Whether Any Intersection in a City is Reachable from Any Other

求有向图的强连通分量的个数

May 16, 2017

题目链接：pdf

题目给出一个有向图，要求输出图中强连通分量的个数。

我把这样的强连通分量叫做一个sink：不存在一个边从这个强连通分量中的任意一个点连接到其它连通分量。也就是说如果把这个强连通分量缩成一个点的话，它的出度为0。

我把和一个图的所有边都反向的图叫做反向图。貌似没有这样的术语。不知道 reverse graph应该怎么翻译。

思路大概是这样的：

如果我们知道一个有向图的sink中的一个点，那么我们就可以求出这个强连通分量的所有点，因为强连通分量中的任意两个点都相互可达。
如何求有相同的sink？我们知道反向图的强连通分量的个数和原图的强连通分量一定是一样的，只是方向不同。并且，原图的sink对应于反向图的 source strong connected component，所以我们可以通过求反向图的source SCC，来求原图的sink。
求一个图的source SCC的思路和用DFS求拓扑排序的思路是一样的，我们可以按照所有点的DFS回退的时刻降序排序，这样DFS最晚回退的点就是反向图的 source SCC，也就是原图的sink，我们可以第二次DFS得到这个sink中的所有点并且从原图中去掉，继续求下一个sink，同时计数。

实现的过程中出现了非常难以发现的bug：一个vector，我在dfs里面加入元素，然后在调用dfs的外层循环中循环这个vector。所以对于小数据并没有显现出错误，对于10000的数据就出现段错误了。调试了很久，不过xhe也教了我好多调试的方法，比如gdb，valgrind，libsigseg库，strace等。不过gdb调试的时候查看STL数据结构里面的数据的时候还是有点小麻烦，这个时候IDE的调试工具就好用很多了。

另外，gdb设置端点竟然支持条件表达式，这个功能非常有用。

// Sat May 13 09:28:34 CST 2017
// Sat May 13 10:46:30 CST 2017

// 求一个有向图的强连通分量的个数。。。

/*
1. 建reverse graph
2. 降序排序post
3. 在原图中依次求强连通分量，并且从图中去掉
 */

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

using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PII;
int cnt;
vector<PII> post;		// index, post

void dfs(vector<VI> &adj, vector<bool> &used, int x, bool get_post)
{
  used[x] = true;
  
  for (auto &v1 : adj[x]) {
    if (!used[v1]) {
      dfs(adj, used, v1, get_post);
    }
  }

  if (get_post) {
    cnt++;
    post.push_back(make_pair(x, cnt));
  }
}

int number_of_strongly_connected_components(vector<VI> &adj) {
  int result = 0;
  vector<VI> rev_adj(adj.size(), VI());
  vector<bool> used(adj.size(), false);
  vector<bool> visit(adj.size(), false);

  for (size_t i = 0; i < adj.size(); ++i) {
    for (auto &v2 : adj[i]) {
      rev_adj[v2].push_back(i);
    }
  }

  // 求reverse graph的post，得到原图的sink Strong Connected Component
  for (size_t i = 0; i < rev_adj.size(); ++i) {
    if (!used[i]) {
      dfs(rev_adj, used, i, true);
    }
  }

  sort(post.begin(), post.end(),
       [](const PII &a, const PII &b) -> bool { return a.second > b.second; });

  // 靠。。。我知道了！！！我真傻。。。竟然一边在dfs里面修改post，一边
  // 循环post。。所以SIGSEGV错误应该是无穷递归的原因。。。或者栈溢出？
  
  // 从原图的sink SCC开始求所有的SCC的个数。。
  for (auto &p : post) {
    if (!visit[p.first]) {
      result++;
      dfs(adj, visit, p.first, false);
    }
  }

  return result;
}

int main() {
  size_t n, m;

  while (std::cin >> n >> m) {
    cnt = 1;

    vector<vector<int> > adj(n, VI());
    post.clear();

    for (size_t i = 0; i < m; i++) {
      int x, y;
      std::cin >> x >> y;
      adj[x - 1].push_back(y - 1);
    }
    std::cout << number_of_strongly_connected_components(adj) << endl;
  }
  
  return 0;
}

Read more