4.Is it a tree?
Check if a given graph is tree or not
An undirected graph is tree if it has following properties. 1) There is no cycle. 2) The graph is connected.
Solution I:(Using BFS)
#include <bits/stdc++.h>
using namespace std;
bool bfs(int node, vector<int> v[], vector<bool> &vs, vector<int> &parent)
{
queue<int> q;
q.push(node);
vs[node] = 1;
parent[node] = node;
while (!q.empty())
{
int x = q.front();
q.pop();
for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
{
if (vs[*itr] == 0)
{
q.push(*itr);
vs[*itr] = 1;
parent[*itr] = x;
}
// If an adjacent is visited and not parent of current
else if (vs[*itr] == 1 && parent[x] != *itr)
{
return false;
}
}
}
return true;
}
int main()
{
int n, m;
cin >> n >> m;
vector<int> v[n + 1];
vector<bool> vs(n + 1);
vector<int> parent(n + 1);
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
bool x = bfs(1, v, vs, parent);
if (!x)
{
cout << "NO";
}
else
{
int res = 0;
for (int i = 1; i <= n; i++)
{
if (vs[i] == 0)
{
res = 1;
break;
}
}
if (res == 1)
{
cout << "NO";
}
else
{
cout << "YES";
}
}
return 0;
}
Solution II: (Using Disjoint sets)
#include <bits/stdc++.h>
using namespace std;
int findPar(vector<int> &v, int node)
{
if (v[node] == -1)
{
return node;
}
v[node] = findPar(v, v[node]);
return v[node];
}
bool uni(vector<int> &v, vector<int> &rank, int a, int b)
{
int parA = findPar(v, a);
int parB = findPar(v, b);
if (parA == parB)
{
return false;
}
if (rank[parA] > rank[parB])
{
v[parB] = parA;
}
else if (rank[parB] > rank[parA])
{
v[parA] = parB;
}
else
{
v[parA] = parB;
rank[parB]++;
}
return true;
}
int main()
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> nodes;
vector<int> v(n + 1, -1);
vector<int> rank(n + 1, 0);
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
nodes.push_back({a, b});
}
int res = 0;
for (auto itr = nodes.begin(); itr != nodes.end(); itr++)
{
pair<int, int> p = *itr;
bool x = uni(v, rank, p.first, p.second);
if (!x)
{
res = 1;
break;
}
}
if (res != 1)
{
int count = 0;
for (int k = 1; k <= n; k++)
{
if (v[k] == -1)
{
count++;
}
if (count > 1)
{
res = 1;
break;
}
}
}
if (res == 1)
{
cout << "NO";
}
else
{
cout << "YES";
}
return 0;
}
Last updated