Advertisement
vahook

Untitled

Mar 29th, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. /* Feladat: Mester / Gráfok, szélességi bejárás / Adott ponton átmenő legrövidebb kör */
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <queue>
  6. #include <stack>
  7. #include <climits>
  8.  
  9. #define MAXN    10000
  10. #define MAXM    200000
  11.  
  12. using namespace std;
  13.  
  14. int N, M, P;
  15. vector<int> ponts[MAXN+1];
  16. int szint[MAXN+1];
  17. int ancestor[MAXN+1];
  18.  
  19. int
  20. main()
  21. {
  22.     ios_base::sync_with_stdio(false);
  23.     cin >> N >> M >> P;
  24.  
  25.     for(int i = 0; i < M; i++){
  26.         int a, b;
  27.         cin >> a >> b;
  28.         ponts[a].push_back(b);
  29.         ponts[b].push_back(a);
  30.     }
  31.  
  32.     queue<int> sor;
  33.     sor.push(P);
  34.     sor.push(0);
  35.    
  36.     int hossz = 2;
  37.     int minn = INT_MAX;
  38.     int a, b;
  39.  
  40.     szint[P] = 1;
  41.     do{
  42.         int most = sor.front();
  43.         sor.pop();
  44.         if(!most){
  45.             hossz++;
  46.             if(minn != INT_MAX){
  47.                 cout << (minn-1) << endl;
  48.  
  49.                 stack<int> ss;
  50.                 ss.push(a);
  51.                 do{
  52.                     a = ancestor[a];
  53.                     ss.push(a);
  54.                 }while(a != P);
  55.                 do{
  56.                     int kk = ss.top();
  57.                     ss.pop();
  58.                     cout << kk << " ";
  59.                 }while(!ss.empty());
  60.                 do{
  61.                     cout << b << " ";
  62.                     b = ancestor[b];
  63.                 }while(b != P);
  64.                 cout << endl;
  65.                
  66.                 return 0;
  67.             }
  68.             sor.push(0);
  69.         }else{
  70.             for(const auto c : ponts[most]){
  71.                 if(!szint[c]){
  72.                     ancestor[c] = most;
  73.                     szint[c] = hossz;
  74.                     sor.push(c);
  75.                 }else if(c != ancestor[most]){
  76.                     int tm = szint[c] + szint[most];
  77.                     if(tm < minn){
  78.                         minn = tm;
  79.                         a = c;
  80.                         b = most;
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.     }while(!sor.empty());
  86.  
  87.     cout << "-1" << endl;
  88.  
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement