fork download
copy 
  1. /* SNET - Solution */
  2.  
  3. #include<iostream>
  4. #include<string>
  5. #include<vector>
  6. #include<set>
  7. #include<algorithm>
  8. using namespace std;
  9.  
  10. int size;
  11. vector < pair <string,int> > data;
  12. string name;
  13. string na[200000];
  14. int visited[200000];
  15. set <string> names;
  16. vector < vector<int> > adj(200000);
  17.  
  18. int search(string x)
  19. {
  20.     int first=0,last=(size-1);
  21.     int mid=(first+last)/2;
  22.     while( first < last )
  23.     {
  24.         if( x > na[mid] ) first=mid+1;
  25.         else last=mid;
  26.         mid=(first+last)/2;
  27.     }
  28.     if(na[mid]!=x) return -1;
  29.     return mid;
  30. }
  31.  
  32. int dfs(int index)
  33. {
  34.     if(visited[index]==1) return 0;
  35.     visited[index]=1;
  36.     int to_ret=1;
  37.     for(vector<int>::iterator itr=adj[index].begin();itr!=adj[index].end();itr++)
  38.     {
  39.         to_ret += dfs(*itr);
  40.     }
  41.     return to_ret;
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47.     string edge[100000][2];
  48.     int k;
  49.     cin>>name;
  50.     cin>>k;
  51.     for(int i=0;i<k;i++)
  52.     {
  53.         string n1,n2;
  54.         cin>>n1>>n2;
  55.         names.insert(n1);
  56.         names.insert(n2);
  57.         edge[i][0] = n1;
  58.         edge[i][1] = n2;
  59.     }
  60.     size=names.size();
  61.     for(int i=0;i<size;i++) visited[i]=0;
  62.     int ii=0;
  63.     for(set <string>::iterator itr=names.begin();itr!=names.end();itr++)
  64.     {
  65.         na[ii]=*itr;
  66.         ii+=1;
  67.     }
  68.  
  69.     for(int i=0;i<k;i++)
  70.     {
  71.         adj[search(edge[i][0])].push_back(search(edge[i][1]));
  72.         adj[search(edge[i][1])].push_back(search(edge[i][0]));
  73.     }
  74.  
  75.     string store_name="";
  76.     int maxx = 0;
  77.     int index = search(name);
  78.     sort(adj[index].begin(),adj[index].end());
  79.     visited[index]=1;
  80.     for(vector<int>::iterator itr = adj[index].begin(); itr!=adj[index].end(); itr++  )
  81.     {
  82.         int store = dfs(*itr);
  83.         if(store > maxx)
  84.         {
  85.             maxx=store;
  86.             store_name=na[*itr];
  87.         }
  88.     }
  89.     cout<<store_name<<"\n"<<maxx<<"\n";
  90.  
  91.     return 0;
  92. }
Success #stdin #stdout 0s 5568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/I4dvAF
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!