You are given a graph with n nodes and m edges. Calculate maximum number of edges that can be removed from the graph so that it contains exactly k connected components.
Input
The first line contains n,m,k(in order).
The next m lines have 2 numbers,ui and vi that showS there is an edge between those nodes. It is guaranteed that input is valid(no multiple edges and no loops).
Output
Maximum number of edges that can be removed from the graph such that it contains exactly k connected components. If the graph intially has more than k components print -1 .
Here is my solution
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>graph(n+1);
while(m--)
{
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<bool>visited(n+1,false);
queue<int>q;
int connected_components=0;
int span_edges=0;
for(int i=1;i<=n;i++)
{
if(visited[i] == false)
{
visited[i]=true;
q.push(i);
while(!q.empty())
{
int top=q.front();
q.pop();
for(auto k : graph[i])
{
if(!visited[k])
{
visited[k]=true;
span_edges++;
q.push(k);
}
}
}
}
connected_components++;
}
if(k<connected_components)
{
cout<<-1<<endl;;
}
else
{
cout<<((m-span_edges)+(k-connected_components))<<endl;
}
}
I got wring answer however I think the logic is right . I am not much familiar with graphs problems, altough I had read all the graph concepts, can someone please help me?
Thanks.
