SHARE
TWEET

Untitled

Promi1707052 Sep 21st, 2019 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<math.h>
  4. #include<vector>
  5. #include<set>
  6. #include<queue>
  7. #include<algorithm>
  8. #include<cstring>    //for memset
  9. using namespace std;
  10.  
  11. #define lli                      int long long
  12. #define ull                      unsigned long long
  13. #define ld                       long double
  14. #define pi                       acos(-1)
  15. #define pb                       push_back
  16. #define pbk                      pop_back
  17. #define mp                       make_pair
  18. #define ff                       first
  19. #define ss                       second
  20. #define pii                      pair<int,int>
  21. #define gcd(a,b)                 __gcd(a,b)
  22. #define lcm(a,b)                (a/gcd(a,b))*b
  23. #define READ                     freopen("in.txt","r",stdin);
  24. #define WRITE                    freopen("outer.txt","w",stdout);
  25. //#define sort(t)                  sort(t.begin(),t.end())
  26. #define mem(a,b)                 memset(a,b,sizeof a)
  27. #define sf                       scanf
  28. #define pf                       printf
  29. #define cs(p)                    printf("Case %d: ", ++(p))
  30. #define dist(ax,ay,bx,by)        sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))
  31. #define MM                       100003
  32. #define inf                      10000000000000000+7
  33. #define M                        1000000002
  34. #define MINI                     -1000000003
  35. //const int fx[]={+1,-1,+0,+0};
  36. //const int fy[]={+0,+0,+1,-1};
  37. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
  38. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
  39.  
  40. //#define for(i,a,n)    for(int i=a;i<n;i++)
  41. //it=myset.find(20);
  42. //int a[8]= {0,0,-1,1,-1,1,-1,1};
  43. //int b[8]= {-1,1,0,0,-1,1,1  ,-1};
  44. vector<int>v[105];
  45. int A[105],B[105];
  46. bool vis[105];
  47. int un=0,f=0;
  48. map<int,int>mm;
  49. int bfs(int s)
  50. {
  51.     vis[s]=1;
  52.     queue<int>q;
  53.     q.push(s);
  54.     while(!q.empty())
  55.     {
  56.         int uu=q.front();
  57.         q.pop();
  58.         un=uu;
  59.         for(int i=0;i<v[uu].size();i++)
  60.         {
  61.             int rr=v[uu][i];
  62.             if(vis[rr]==0)
  63.             {
  64.                 vis[rr]=1;
  65.                 q.push(rr);
  66.             }
  67.         }
  68.     }
  69.     return un;
  70.  
  71. }
  72. void bfs_print(int s)
  73. {
  74.     vis[s]=1;
  75.     queue<int>q;
  76.     q.push(s);
  77.     while(!q.empty())
  78.     {
  79.         int uu=q.front();
  80.         q.pop();
  81.         for(int i=0;i<v[uu].size();i++)
  82.         {
  83.             int rr=v[uu][i];
  84.             if(vis[rr]==0)
  85.             {
  86.                 if(mm[uu]==1)
  87.                 {
  88.                     A[f]=uu;
  89.                     B[f]=uu;
  90.                     f++;
  91.                     A[f]=uu;
  92.                     B[f]=rr;
  93.                     f++;
  94.                     //cout<<uu<<" "<<uu<<endl;
  95.                     //cout<<uu<<" "<<rr<<endl;
  96.                 }
  97.                 else if(mm[rr]==1)
  98.                 {//cout<<uu<<" "<<rr<<endl;
  99.                 //cout<<rr<<" "<<rr<<endl;
  100.                 A[f]=uu;
  101.                     B[f]=rr;
  102.                     f++;
  103.                     A[f]=rr;
  104.                     B[f]=rr;
  105.                     f++;
  106.                 }
  107.                 else {//cout<<uu<<" "<<rr<<endl;
  108.                     A[f]=uu;
  109.                     B[f]=rr;
  110.                     f++;
  111.                 }
  112.                 vis[rr]=1;
  113.                 q.push(rr);
  114.             }
  115.         }
  116.     }
  117.  
  118. }
  119. int main()
  120. {
  121.     int i,j,n,u=-1;
  122.     cin>>n;
  123.     int a[n+5],b[n+5];
  124.  
  125.     for(i=0;i<n;i++)
  126.     {
  127.         cin>>a[i]>>b[i];
  128.  
  129.         if(a[i]!=b[i])
  130.         {
  131.             v[a[i]].pb(b[i]);
  132.             v[b[i]].pb(a[i]);
  133.         }
  134.         else if(a[i]==b[i])
  135.         {
  136.            mm[a[i]]=1;
  137.         }
  138.     }
  139.     int t1=bfs(3);
  140.     memset(vis,0,sizeof vis);
  141.     bfs_print(t1);
  142.     for(i=0;i<f;i++)
  143.     {
  144.         //cout<<A[i]<<" "<<B[i]<<endl;
  145.         for(j=0;j<n;j++)
  146.         {
  147.             //cout<<"u "<<a[j]<<" "<<b[j]<<endl;
  148.             if(A[i]==a[j] && B[i]==b[j])
  149.             {
  150.                 cout<<j+1<<" a"<<endl;
  151.                 break;
  152.             }
  153.             else if(A[i]==b[j] && B[i]==a[j])
  154.             {
  155.                 cout<<j+1<<" b"<<endl;
  156.                 break;
  157.             }
  158.         }
  159.     }
  160.     return 0;
  161. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top