DFS with passing variables
unknown
c_cpp
a year ago
1.0 kB
1
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