1.DFS

Similar to Pre Order Traversal

Solution

#include <bits/stdc++.h>

using namespace std;

void dfs(int node, vector<int> v[], vector<bool> &vs)
{
    if (vs[node] == 0)
    {
        vs[node] = 1;
        for (auto itr = v[node].begin(); itr != v[node].end(); itr++)
        {
            if (vs[*itr] == 0)
            {
                dfs(*itr, v, vs);
            }
        }
    }
    return;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v[n + 1];
    vector<bool> vs(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);
    }

    int node;
    cin >> node;
    dfs(node, v, vs);
	int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vs[i] == 0)
        {
            count++;
        }
    }
    cout << count;
}

Time Complexity: O(V+E)