fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <bitset>
  8. #include <algorithm>
  9. #include <stack>
  10. #include <queue>
  11. #include <list>
  12. #include <deque>
  13. #include <string>
  14. #include <iomanip>
  15. #include <numeric>
  16. #include <functional>
  17. #include <string.h>
  18. #include <new>
  19. #include <utility>
  20. #include <cassert>
  21. #include <climits>
  22. # define LIMIT 102
  23. using namespace std;
  24. vector<int>TMP_IP;
  25. char Adjacency[LIMIT][LIMIT];
  26. vector<vector<int> >ADJ_vector(LIMIT);
  27. int MARKED[LIMIT];
  28. vector<int>connected_COMPONENTS;
  29. vector<int>Positions_vector;
  30. void DepthFirstTraversal(int u)
  31. {
  32.      MARKED[u]=1;
  33.      connected_COMPONENTS.push_back(u);
  34.      for(int j=0;j<ADJ_vector[u].size();++j)
  35.           if(!MARKED[ADJ_vector[u][j]] )
  36.              DepthFirstTraversal(ADJ_vector[u][j]);
  37. }
  38. //Print result
  39. void lexo_smallest(int K)
  40. {
  41.      for(int i=0;i<K;++i)
  42.                   cout<<TMP_IP[i]<<" ";
  43.              cout<<endl;
  44. }
  45. int main()
  46. {
  47.     int K,ip;
  48.     string rows[109];
  49.     scanf("%d",&K);
  50.     for(int i=0;i<K;++i)
  51.     {
  52.             scanf("%d",&ip);
  53.             TMP_IP.push_back(ip);
  54.     }
  55.  
  56.     for(int i=0;i<K;++i)
  57.                cin>>rows[i];
  58.  
  59.  
  60.     for(int i=0;i<K;++i)
  61.          for(int j=0;j<rows[i].size();++j)
  62.              Adjacency[i][j]=rows[i][j];
  63.  
  64.  
  65.     for(int i=0;i<K;++i)
  66.     for(int j=0;j<K;++j)
  67.      if(Adjacency[i][j]=='Y')
  68.          ADJ_vector[i].push_back(j);  
  69.  
  70.             for( int i = 0 ; i <K ; ++i )
  71.             {   
  72.                 if( !MARKED[ i ] )
  73.                 { 
  74.  
  75.                     DepthFirstTraversal( i ); 
  76.                     for(int x=0;x<connected_COMPONENTS.size();++x)
  77.                     {
  78.                             Positions_vector.push_back(TMP_IP[connected_COMPONENTS[x]]);
  79.                     }
  80.                     sort(connected_COMPONENTS.begin(),connected_COMPONENTS.end());
  81.                     sort(Positions_vector.begin(),Positions_vector.end());
  82.                     for(int x=0;x<connected_COMPONENTS.size();++x)
  83.                     {
  84.                             TMP_IP[connected_COMPONENTS[x]]=Positions_vector[x];
  85.                     }
  86.                     connected_COMPONENTS.clear();
  87.                     Positions_vector.clear();
  88.  
  89.                 }
  90.             }
  91.             lexo_smallest(K);
  92.  
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 3000KB
comments (?)
stdin
copy 
3
3 2 1
NYN
YNY
NYN
stdout
copy 
1 2 3
https://ideone.com/wM3FEU
language:
C++ (gcc 8.3)
created:
12 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!