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;
}