G2A Many GEOs
SHARE
TWEET

dfs

a guest Apr 4th, 2020 110 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5;
  4. map<string, int> mp;
  5. int n,m, comp = 0;
  6. vector<int> g[N+5];
  7. int  vis[N+5];
  8.  
  9. int DFS(int pos){
  10.     vis[pos] = 1;
  11.     for(int i = 0; i < g[pos].size(); i++){
  12.         int ne = g[pos][i];
  13.         if(!vis[ne]){
  14.             comp++;
  15.             DFS(ne);
  16.         }
  17.     }
  18.     return comp;
  19. }
  20.  
  21. int main(){
  22.     string c, x, y;
  23.     int ans = 0;
  24.     while(true){
  25.         cin >> n >> m;
  26.         if(n == 0 && m == 0) break;
  27.         for(int i = 1; i <= n; i++){
  28.             cin >> c;
  29.             mp.insert(make_pair(c,i));
  30.             g[i].push_back(0);
  31.         }
  32.         for(int i = 1; i <= m; i++){
  33.             cin >> x >> y;
  34.             g[mp[x]].push_back(mp[y]);
  35.             g[mp[y]].push_back(mp[x]);
  36.         }
  37.         for(int i = 1; i <= n; i++){
  38.             ans  = max(ans,DFS(i));
  39.         }
  40.         cout << ans << endl;
  41.         ans = 0; comp = 0;
  42.         memset(vis, 0, sizeof(vis));memset(g, 0, sizeof(g));
  43.        
  44.     }
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top