DFS with passing variables
unknown
c_cpp
2 years ago
1.0 kB
5
Indexable
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void dfs(int u, vector<int>g[], vector<bool> &visited,int &size){
visited[u]=true;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(visited[v]==false){
size++;
dfs(v,g,visited,size);
}
}
return;
}
void solve()
{
int n,m,k;
cin>>n>>m>>k;
vector<int>g[n+1];
vector<bool> visited(n+1, false);
vector<int> values;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<n+1;i++){
int size=1;
if(visited[i]==false){
dfs(i,g,visited,size);
values.push_back(size);
}
}
sort(values.begin(), values.end());
int tot=values.size();
int sum=values[tot-1];
for(int i=tot-2;i>=0 && k-- ;i--){
sum+=values[i];
}
cout<<sum<<endl;
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
solve();
return 0;
}Editor is loading...
Leave a Comment