# Treating input as graph, making sure no cycles and one connected component.

• There is probably an easier way to do this.... This is the first thing that came to my mind:

I treat the input as an undirected graph, and

1. Make sure there are no cycles.
2. Check if it is just one connected component.
``````class Solution {

typedef unordered_set<int> Bucket;

vector<bool> visited;
vector<int> ccParent;

void initialize(int n, vector<pair<int, int>>& edges) {
visited  = vector<bool>(n, false);
ccParent = vector<int>(n, -1);
for (int i=0; i<n; i++) { adjList.push_back(Bucket()); }
for (const pair<int, int>& pft : edges) {
}
}

bool dfs(int parent, int node, int ccpar) {
visited[node]  = true;
ccParent[node] = ccpar;
for (const int& neigh : adjList[node]) {
if (neigh == parent) continue; //skip parent
if (visited[neigh]) return false;
if (dfs(node, neigh, ccpar) == false) return false;
}
return true;
}

public:

bool validTree(int n, vector<pair<int, int>>& edges) {
initialize(n, edges);

for (int n=0; n<adjList.size(); n++) {
if (visited[n]) continue;
if (dfs(-1, n, n) == false) return false; //detected cycle
}
int ccpar = ccParent[0];
for (int i=1; i<adjList.size(); i++) {
if (ccParent[i] != ccpar) return false; //not one connected component
}
return true;
}
};``````

• I just realized that this probably doesn't handle self-loops or parallel edges. I'll need to create a test case or two, and handle it during the initialization part.

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