graph valid tree
solution
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.
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.
利用并查集判断一个edge的左边和右边是否在一个set中,是的话Return false。
http://www.lintcode.com/en/problem/graph-valid-tree/
code
class unionfind {
public:
map<int, int> hash;
unionfind(int n)
{
for(int i = 0; i<n; i++)
{
hash[i] = i;
}
}
int find(int key)
{
while(key != hash[key])
{
key = hash[key];
}
return key;
}
int ufind(int key)
{
int boss = find(key);
while(key != boss)
{
key = hash[key];
hash[key] = boss;
}
return boss;
}
bool unionboss(int a, int b)
{
int bossa = ufind(a);
int bossb = ufind(b);
if(bossa == bossb)
{
return false;
}
else
{
hash[bossa] = bossb;
return true;
}
}
};
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
int size = edges.size();
if(n == 1 && size == 0)
{
return true;
}
if(size == 0)
{
return false;
}
unionfind uf(n);
for(pair<int, int> p : edges)
{
if(uf.unionboss(p.first, p.second) == false)
{
return false;
}
}
int boss = uf.ufind(0);
for(int i = 1; i<n; i++)
{
if(uf.ufind(i) != boss)
{
return false;
}
}
return true;
}
};
code
class UnionFind {
public:
map<int, int> hash;
void addNode(int key, int val)
{
hash[key] = val;
}
int find(int key)
{
while(key != hash[key])
{
key = hash[key];
}
return key;
}
int compress_find(int key)
{
int boss = find(key);
while(key != boss)
{
int next = hash[key];
hash[key] = boss;
key = next;
}
return boss;
}
void bossunion(int key1, int key2)
{
int boss1 = compress_find(key1);
int boss2 = compress_find(key2);
if(boss1 != boss2)
{
hash[boss1] = boss2;
}
}
};
class Solution {
public:
/**
* @param n an integer
* @param edges a list of undirected edges
* @return true if it's a valid tree, or false
*/
bool validTree(int n, vector<vector<int>>& edges) {
// Write your code here
if(edges.size() == 0)
{
if(n == 1)
{
return true;
}
else
{
return false;
}
}
UnionFind uf;
for(vector<int> tmp : edges)
{
int left = tmp[0];
int right = tmp[1];
if(uf.hash.find(left) == uf.hash.end())
{
uf.addNode(left, left);
}
if(uf.hash.find(right) == uf.hash.end())
{
uf.addNode(right, right);
}
if(uf.compress_find(left) == uf.compress_find(right))
{
return false;
}
else
{
uf.bossunion(left, right);
}
}
if(uf.hash.size() != n)
{
return false;
}
return true;
}
};