Advertisement
kburnik

C++ - Zadatak Otoci

Jan 7th, 2013
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. map <string, int> used;
  10. map < string , map <string, int> > nodes;
  11. vector <string> groups;
  12.  
  13. void findgroups(string node,int level) {
  14.    if (!used[node]) {
  15.        if (level == 0 ) groups.push_back("");
  16.        used[node] = 1;
  17.        groups.back() += node;
  18.        
  19.        map <string, int>::iterator jt;
  20.        for (jt = nodes[node].begin(); jt != nodes[node].end() ; jt++) {
  21.             findgroups(jt->first,level+1);
  22.        }
  23.     }
  24. }
  25.  
  26.  
  27. int main() {
  28.        
  29.     int n;    
  30.     cin >> n;
  31.    
  32.     string src, ref;
  33.     for (int i = 0 ; i < n ; i++) {
  34.         cin >> src >> ref;
  35.         used[src] = used[ref] = 0;
  36.         nodes[src][ref] = nodes[ref][src] = 1;
  37.     }
  38.  
  39.    map < string , int >::iterator nk;
  40.    for (nk = used.begin() ; nk != used.end(); nk++) {
  41.         findgroups(nk->first,0);
  42.    }
  43.  
  44.    vector <string>::iterator git;  
  45.    sort(groups.begin(),groups.end());
  46.    for (git = groups.begin(); git != groups.end(); git++) {
  47.         sort(git->begin(),git->end());
  48.         cout << *git << endl;
  49.     }
  50.  
  51.     // system("pause");
  52.    
  53.     return 0;    
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement