leetcode 261 Graph Valid Tree 图验证树

Posted on | In |

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

这道题给了我们一个无向图，让我们来判断其是否为一棵树，我们知道如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以我们的焦点就变成了验证是否是连通图和是否含有环。我们首先用DFS来做，根据pair来建立一个图的结构，用邻接链表来表示，还需要一个一位数组v来记录某个节点是否被访问过，然后我们用DFS来搜索节点0，遍历的思想是，当DFS到某个节点，先看当前节点是否被访问过，如果已经被访问过，说明环存在，直接返回false，如果未被访问过，我们现在将其状态标记为已访问过，然后我们到邻接链表里去找跟其相邻的节点继续递归遍历，注意我们还需要一个变量pre来记录上一个节点，以免回到上一个节点，这样遍历结束后，我们就把和节点0相邻的节点都标记为true，然后我们在看v里面是否还有没被访问过的节点，如果有，则说明图不是完全连通的，返回false，反之返回true

验证是否是连通图和是否含有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;

class Solution {
public:
	vector<vector<int> > g;
    bool validTree(int n, vector<pair<int, int> >& edges) {
    	g=vector<vector<int> >(n,vector<int>());
        for(pair<int, int> t:edges){
  
        	g[t.first].push_back(t.second);
        	g[t.second].push_back(t.first); 
		}
		 vector<bool> v(n, false);
        if(!dfs(0,-1,v)) 
		{
			return false;
		}
        for(auto a:v){
        	if(!a) {
        		return false;
			}
		}
		return true;
   }
   //传参 传的是引用  
   bool dfs(int cur,int pre,vector<bool> &v){
   	if(v[cur])   return false;
   	v[cur]=true;
   	cout<<cur<<endl;
   	for(auto a: g[cur])
   	{
   		if(a==pre) continue;
   		if(!dfs(a,cur,v)) return false;
	}
	return true;
   }
};
int main(){
	 vector<pair<int, int> > edges; 
	 edges.push_back(pair<int,int>{0,1});
	 edges.push_back(pair<int,int>{0,2});	 
	 edges.push_back(pair<int,int>{0,3});
	 edges.push_back(pair<int,int>{1,4});	 
	 Solution so;	     
	 if(so.validTree(5,edges)) cout<<"t"<<endl;
	 else cout<<"f"<<endl;
	
}

参考
http://www.cnblogs.com/grandyang/p/5257919.html