# C#: Easy to Understand Algorithm with Explanation. (Accepted)

• A graph is a valid tree when it satisfies the following two conditions:

1. There is no cycle in the graph.
2. Every node is reached (has to be a connected graph)

My solution is based on the Union-Find algorithm

Solution 1: Exact representation (template) of the algorithm.

``````public class Solution {
int[] parent;
public bool ValidTree(int n, int[,] edges)
{
int edgeCount = edges.Length / 2;
//An undirected tree with n nodes must have exactly n−1 edges.
if (edgeCount != n - 1)
return false;
//Initializing parent to -1 for all vertices.
this.parent = new int[n];
for (int i = 0; i < n; i++)
this.parent[i] = -1;
for (int i = 0; i < edgeCount; i++)
{
//Extracting vertices of an edge.
int elementOne = edges[i, 0];
int elementTwo = edges[i, 1];
//Find
if (Find(elementOne) == Find(elementTwo))
return false;
else
Union(elementOne, elementTwo);   //Union
}
return true;
}
private int Find(int element)
{
if (this.parent[element] == -1)
return element;
else
return Find(this.parent[element]);
}
private void Union(int elementOne, int elementTwo)
{
int parentOne = Find(elementOne);
int parentTwo = Find(elementTwo);
parent[parentOne] = parentTwo;
}
}
``````

Solution 2: Cleaner/Optimized version of above algorithm.

``````public class Solution {
int[] parent;
public bool ValidTree(int n, int[,] edges) {
int edgeCount = edges.Length / 2;
//An undirected tree with n nodes must have exactly n−1 edges.
if (edgeCount != n - 1)
return false;
//Initializing parent to -1 for all vertices.
this.parent = new int[n];
for (int i = 0; i < n; i++)
this.parent[i] = -1;
for (int i = 0; i < edgeCount; i++)
{
//Extracting vertices of an edge.
int elementOne = edges[i, 0];
int elementTwo = edges[i, 1];
//Find
int parentOne = Find(elementOne);
int parentTwo = Find(elementTwo);
if (parentOne == parentTwo)
return false;
else
this.parent[parentOne] = parentTwo;     //Union
}
return true;
}
private int Find(int element)
{
if (this.parent[element] == -1)
return element;
else
return Find(this.parent[element]);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.