DFS with passing variables

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.0 kB
0
Indexable
Never
#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;
}
Leave a Comment