Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- const int MAX = 1e5+10;
- vector<int> g[MAX];
- int vis[MAX];
- map<string, int> m;
- int dfs(int v){
- vis[v] = 1;
- int ret = 1;
- for(int i = 0; i < g[v].size(); i++)if(!vis[g[v][i]]){
- ret += dfs(g[v][i]);
- }
- return ret;
- }
- int main(){
- memset(vis, 0, sizeof(vis));
- ios::sync_with_stdio(0);
- int n, pr, k;
- int t = 0;
- cin >> n >> pr >> k;
- for(int i = 0; i < pr; i++){
- string s, ss;
- cin >> s >> ss;
- int x, y;
- auto it = m.find(s);
- if(it == m.end()){
- x = m[s] = t++;
- }else{
- x = it->second;
- }
- auto it2 = m.find(ss);
- if(it2 == m.end()){
- y = m[ss] = t++;
- }else{
- y = it2->second;
- }
- g[x].push_back(y);
- g[y].push_back(x);
- }
- vector<int> v;
- int ans = 0;
- for(int i = 0; i < n; i++){
- if(!vis[i]){
- v.push_back(dfs(i));
- }
- }
- sort(v.begin(), v.end());
- reverse(v.begin(), v.end());
- for(int i = 0; i < k and i < v.size(); i++)
- ans += v[i];
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement