fork download
copy 
  1. //MEHNAT
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define tr(c, it) \
  6. for(auto it = c.begin(); it != c.end(); it++)
  7. #define ll long long
  8.  
  9. //const int MAX=1e3 + 5;
  10. int a[1000][1000];
  11.  
  12. bool flag=0;
  13.  
  14. bool adj(int a[][1000],int n){
  15.     for(int i=1;i<=n;i++){
  16.         for(int j=i;j<=n;j++){
  17.             if(a[i][j]==1)
  18.                 return true;
  19.         }
  20.     }
  21.     return false;
  22.  
  23. }
  24.  
  25. int main(){
  26.     int n,x,y;
  27.  
  28.     vector<pair <int,pair <int,int> > > ans;
  29.  
  30.     cin>>n;
  31.  
  32.     for(int i=1;i<=n;i++){
  33.         for(int j=1;j<=n;j++){
  34.             a[i][j]=0;
  35.         }
  36.     }
  37.  
  38.     for (int i=1;i<n;i++){
  39.         cin>>x>>y;
  40.         a[x][y]=1;
  41.     }
  42.  
  43. //        Display
  44.     /*
  45.     cout<<"Display"<<endl;
  46.     for(int i=1;i<=n;i++){
  47.         for(int j=1;j<=n;j++){
  48.             cout<<a[i][j]<<" ";
  49.         }
  50.         cout<<endl;
  51.     }
  52.     */
  53.  
  54.    int imp=n;
  55.  
  56.    while(adj(a,n)){
  57.        bool flag1=1;
  58.        int r,c=0;
  59.  
  60.        for(int i=1;i<=imp;i++){
  61.             for(int j=1;j<=imp;j++){
  62.                 if(a[j][i]==1){
  63.                     flag1=0;
  64.                     break;
  65.                 }
  66.             }
  67.             if(flag1){
  68.                 c=i;
  69.                 break;
  70.             }
  71.             else{
  72.                 flag1=1;
  73.             }
  74.         }
  75.         if(c!=imp){
  76.             for(int i=1;i<=n;i++){
  77.                 swap(a[i][imp],a[i][c]);
  78.             }
  79.             ans.push_back(make_pair(2,make_pair(c,imp)));
  80.         }
  81.  
  82.  
  83.         int c1;
  84.         for(int i=1;i<=imp;i++){
  85.             for(int j=1;j<=imp;j++){
  86.                 if(a[i][j]){
  87.                     r=i;
  88.                     c1=j;
  89.                     break;
  90.                 }
  91.             }
  92.             if(a[r][c1])
  93.                 break;
  94.         }
  95.         if(r!=imp){
  96.             for(int i=1;i<=n;i++){
  97.                 swap(a[imp][i],a[r][i]);
  98.             }
  99.             ans.push_back(make_pair(1,make_pair(r,imp)));
  100.         }
  101.         imp--;
  102.     }
  103.  
  104.  
  105.  
  106.     cout<<ans.size()<<endl;
  107.  
  108.     for(int i=0;i<ans.size();i++){
  109.         cout<<ans[i].first<<" "<<ans[i].second.first<<" "<<ans[i].second.second<<endl;
  110.     }
  111.  
  112.     return 0;
  113.  
  114. }
  115.  
  116. /*
  117. check for corner cases(n == 1?)
  118. see the constraint
  119. read the highlighted text again
  120. */
Runtime error #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9mqDlp
language:
C++ (gcc 8.3)
created:
5 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!