1.Maximum number of edges to be removed to contain exactly K connected components in the Graph

Spoj Question

Connected Components

Solution : (Using DFS)

Algo: * Check the no of times DFS is called. * If the Count of DFS is more than k return -1 as removal of edges will give rise to more connected components. * Else return m-n+k.

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int n, m, k;

    cin >> n >> m >> k;
    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 count = 0;
    for (int i = 1; i < n+1; i++)
    {
        if (vs[i] == 0)
        {
            dfs(i, v, vs);
            count++;
        }
    }

    if (count > k)
    {
        cout << -1;
    }
    else
    {
        cout << m - n + k;
    }

    return 0;
}

Time Complexity: O(V+E)