261. Graph Valid Tree
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""] Output: [[""]]
Example 3:
Input: strs = ["a"] Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
判断一个图是不是一颗树，这个问题就得转换为两个充要条件了：
1. 图的vertex n 和边 edge必须满足 vertex -1 = edges
2. 所有的vertex都必须联通的。
第一点可以通过 vertex-1 == edges 来判断。
第二个充要条件就得遍历图，并且记录下顶点数目来判断了。 而遍历图，基本都是用BFS的办法，和遍历树差不多，一层层的往下遍历。
但是遍历图的时候有个和树不一样的点，无向图的边界（0， 1） 中0的邻居是1， 1的邻居是0. 当我们用遍历树的办法遍历图的时候，会发现很多节点重复遍历并有可能形成一个环。
注意到这点，就得有个办法去记录已经遍历过的顶点，当遍历有个邻居A的邻居B已经被访问过了，就不用再去访问B了。
步骤如下：
a) 用queue来记录访问的顶点，并依次的出队列。
b）每次出队列的顶点就得把该顶点的邻居节点push到队列里了。比如A的邻居是B，C，D，E
i). push 邻居节点到队列之前，必须检查下该顶点是不是已经访问过了。
1）访问过了，那就调到下个邻居节点。
2） 没有访问过，那么就push进队列。
c） 重复这个动作直到队列为空。
这道题目有个小坑，没有给出每个顶点的邻居顶点。
得把输入的二维数组转换下为顶点：邻居顶点的格式：
1） 用一个unordered_map来表示顶点以及邻居顶点
比如： 0 {1， 2， 3} 2{0， 1}
unordered_map<int , vector<int>> constructGraph(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graphic;
for(auto &edge: edges) {
graphic[edge[0]].push_back(edge[1]);
graphic[edge[1]].push_back(edge[0]);
}
return graphic;
}
拿到了想要的数据后，接下来就按照上述的步骤做。
queue<int> myqueue;
unordered_set<int> accessedVertex;
vector<int> nodesInGraph;
//unordered_map<int vertex, vector<int> neighbers>
unordered_map<int , vector<int>> graph = constructGraph(edges);
myqueue.push(graph.begin()->first);
accessedVertex.insert(graph.begin()->first);
while(!myqueue.empty()) {
int vertex = myqueue.front();
myqueue.pop();
nodesInGraph.push_back(vertex);
for(auto &neighber: graph[vertex]) {
if(accessedVertex.find(neighber) != accessedVertex.end())
continue;
else {
myqueue.push(neighber);
accessedVertex.insert(neighber);
}
}
最后拼接起来的代码如下：
class Solution {
public:
unordered_map<int , vector<int>> constructGraph(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graphic;
for(auto &edge: edges) {
graphic[edge[0]].push_back(edge[1]);
graphic[edge[1]].push_back(edge[0]);
}
return graphic;
}
bool validTree(int n, vector<vector<int>>& edges) {
// Tree have two property
// 1. vertex n edge n-1
// 2. every node must be connected
if(n ==0)
return false;
if(edges.size() == 0 && n ==1)
return true;
if(edges.size() != n -1)
return false;
queue<int> myqueue;
unordered_set<int> accessedVertex;
vector<int> nodesInGraph;
//unordered_map<int vertex, vector<int> neighbers>
unordered_map<int , vector<int>> graph = constructGraph(edges);
myqueue.push(graph.begin()->first);
accessedVertex.insert(graph.begin()->first);
while(!myqueue.empty()) {
int vertex = myqueue.front();
myqueue.pop();
nodesInGraph.push_back(vertex);
for(auto &neighber: graph[vertex]) {
if(accessedVertex.find(neighber) != accessedVertex.end())
continue;
else {
myqueue.push(neighber);
accessedVertex.insert(neighber);
}
}
}
return nodesInGraph.size() == n;
}
};
总结下我犯的错误把
1. 构建节点和邻居节点的时候按照有向图来构建了。 比如（0， 1）边，构建出来的邻居map应该是 顶点0的邻居是1， 同时顶点1的邻居是0. 我只考虑到了 顶点0的邻居是1，没有考虑到顶点1 的邻居也是0.
2. 什么时候去检查邻居的顶点是不是已经访问过了。
第一次检查的地方是顶点出队列的时候， 比如顶点A出队列，然后判断该顶点是不是已经访问过。 这样肯定是不对的，因为会造成队列里有很多重复的顶点在里面。
正确的地方是元素入栈之前去检查，这样就能保证队列里的元素都是没有访问过的。