[LeetCode]Number of Connected Components in an Undirected Graph

DFS的问题，从每个节点开始DFS，如果之间访问过就说明不是新的component，否则的话mark所有这次DFS能到达的节点，就是新的component，记录数量即可，代码如下：

	class Solution {
	public:
	int countComponents(int n, vector<pair<int, int>>& edges) {
	if (n <= 0)return 0;
	vector<vector<int>> g(n);
	for (auto p : edges)
	{
	g[p.first].push_back(p.second);
	g[p.second].push_back(p.first);
	}
	int res = 0;
	vector<bool> marked(n);
	for(int i = 0; i < n; ++i)
	if(isComponent(g, marked, -1, i))
	++res;
	return res;
	}
	private:
	bool isComponent(vector<vector<int>>& g, vector<bool>& marked, int from, int curr)
	{
	if(marked[curr])
	return false;
	marked[curr] = true;
	for(auto& next : g[curr])
	if(next != from)
	isComponent(g, marked, curr, next);
	return true;
	}
	};

view raw Number of Connected Components in an Undirected Graph.cpp hosted with ❤ by GitHub

链接性的题目Union Find也完全可以，Union Find的做法可以参考Friend Circle。