Advertisement
Guest User

Untitled

a guest
Sep 17th, 2019
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6.  
  7. const int MAX = 1e5+10;
  8.  
  9. vector<int> g[MAX];
  10. int vis[MAX];
  11. map<string, int> m;
  12.  
  13. int dfs(int v){
  14.     vis[v] = 1;
  15.     int ret = 1;
  16.     for(int i = 0; i < g[v].size(); i++)if(!vis[g[v][i]]){
  17.         ret += dfs(g[v][i]);
  18.     }
  19.     return ret;
  20. }
  21.  
  22. int main(){
  23.     memset(vis, 0, sizeof(vis));
  24.     ios::sync_with_stdio(0);
  25.     int n, pr, k;
  26.     int t = 0;
  27.  
  28.     cin >> n >> pr >> k;
  29.  
  30.     for(int i = 0; i < pr; i++){
  31.         string s, ss;
  32.         cin >> s >> ss;
  33.         int x, y;
  34.         auto it = m.find(s);
  35.         if(it == m.end()){
  36.             x = m[s] = t++;
  37.         }else{
  38.             x = it->second;
  39.         }
  40.         auto it2 = m.find(ss);
  41.         if(it2 == m.end()){
  42.             y = m[ss] = t++;
  43.         }else{
  44.             y = it2->second;
  45.         }
  46.         g[x].push_back(y);
  47.         g[y].push_back(x);
  48.     }
  49.     vector<int> v;
  50.     int ans = 0;
  51.     for(int i = 0; i < n; i++){
  52.         if(!vis[i]){
  53.             v.push_back(dfs(i));
  54.         }  
  55.     }
  56.     sort(v.begin(), v.end());
  57.     reverse(v.begin(), v.end());
  58.     for(int i = 0; i < k and i < v.size(); i++)
  59.         ans += v[i];
  60.     cout << ans << endl;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement