Adding Exits to a Maze

题目链接：pdf

给出一个无向图，求连通分量的个数。对这个图做一遍DFS同时计数就好了。因 为我用邻接表表示图，所以还要记得孤点的情况，这个后来才发现。

// Begin: Fri May 12 19:52:46 CST 2017
// Finish: Fri May 12 20:16:44 CST 2017


// 求有几个连通块。。

#include <iostream>
#include <vector>

using namespace std;

void
dfs(vector<vector<int> > &adj, vector<bool> &visit, int x)
{
  visit[x] = true;

  for (size_t i = 0; i < adj[x].size(); ++i) {
    if (!visit[adj[x][i]]) {
      dfs(adj, visit, adj[x][i]);
    }
  }

}

int number_of_components(vector<vector<int> > &adj, int n) {
  int res = 0;
  vector<bool> visit(n, false);

  // 所以我忘了孤点。。。。T_T
  
  for (size_t i = 0; i < adj.size(); ++i) {
    for (size_t j = 0; j < adj[i].size(); ++j) {
      if (!visit[adj[i][j]]) {
	res++;
	dfs(adj, visit, adj[i][j]);
      }
    }
  }

  // 加上孤点。。。。
  for (int i = 0; i < n; ++i) {
    if (!visit[i]) res++;
  }


  return res;
}

int main() {
  size_t n, m;

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