Fronzilla

ej1

May 26th, 2022 (edited)
577
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. #define INF (2 << 22)
  6.  
  7. using namespace std;
  8. struct info
  9. {
  10.     int color;
  11.     int d;
  12.     int padre;
  13. };
  14. struct Arista
  15. {
  16.     int a, b;
  17. };
  18.  
  19. vector<vector<int> > adj;
  20. vector<vector<info> > datos;
  21. vector<Arista> aristas;
  22. bool perteneceAlTree (int raiz, Arista arista)
  23. {
  24.     return (datos[raiz][arista.b].padre == arista.a || datos[raiz][arista.a].padre == arista.b);
  25. }
  26.  
  27. bool distintoNivel(int raiz, Arista arista)
  28. {
  29.     return (datos[raiz][arista.a].d > datos[raiz][arista.b].d || datos[raiz][arista.a].d < datos[raiz][arista.b].d);
  30. }
  31.  
  32. void BFS(int nodos, int &nodoInicial, int &nodoDestino, int &nodoIntermedio)
  33. {
  34.     queue<int>cola;
  35.     for(int raiz = 0; raiz < nodos; raiz++)
  36.     {
  37.         cola.push(raiz);
  38.         while(cola.size() != 0)
  39.         {
  40.             int actual = cola.front();
  41.             for(auto v: adj[actual])
  42.             {
  43.                 if(datos[raiz][v].color == 0)
  44.                 {
  45.                     datos[raiz][v].color = 1;
  46.                     datos[raiz][v].d = datos[raiz][actual].d + 1;
  47.                     datos[raiz][v].padre = actual;
  48.                     cola.push(v);
  49.                 }
  50.             }
  51.             datos[raiz][actual].color = 2;
  52.             cola.pop();
  53.         }
  54.         if(nodoInicial == -1 && nodoDestino == -1)
  55.         {
  56.             for(auto arista: aristas)
  57.             {
  58.                 if(!perteneceAlTree(raiz, arista) && distintoNivel(raiz, arista))
  59.                 {
  60.                     nodoInicial = raiz;
  61.                     nodoIntermedio = (datos[raiz][arista.a].d < datos[raiz][arista.b].d) ? arista.a : arista.b;
  62.                     nodoDestino = (datos[raiz][arista.a].d > datos[raiz][arista.b].d) ? arista.a : arista.b;
  63.                 }
  64.             }
  65.         }
  66.        
  67.     }
  68. }
  69.  
  70. void imprimirCamino(int nodoInicial, int nodoDestino)
  71. {
  72.     if(nodoInicial == nodoDestino)
  73.         cout << nodoInicial << " ";
  74.     else
  75.     {
  76.         imprimirCamino(nodoInicial, datos[nodoInicial][nodoDestino].padre);
  77.         cout << nodoDestino <<" ";
  78.     }
  79. }
  80.  
  81. void mostrarCaminosMinimos(int nodos)
  82. {
  83.     cout << 1 << endl;
  84.     for(int f = 0; f < nodos; f++)
  85.         {
  86.         for(int c = 0; c < nodos; c++)
  87.         {
  88.             cout << datos[f][c].padre << " ";
  89.         }
  90.         cout << endl;
  91.         }  
  92. }
  93.  
  94. void mostrarDosCaminos(int nodoInicial, int nodoIntermedio, int nodoDestino)
  95. {
  96.     cout << 0 << endl;
  97.     imprimirCamino(nodoInicial, nodoDestino);
  98.     cout << endl;
  99.     imprimirCamino(nodoInicial, nodoIntermedio);
  100.     cout << nodoDestino << endl;
  101. }
  102. int main()
  103. {
  104.     int n, m;
  105.     cin >> n >> m;
  106.     //redimension del vector de adyacencias y la matriz de distancias, color y predecesores
  107.     adj.resize(n);
  108.     datos.resize(n, vector<info> (n, {0,INF, -1}));
  109.     int a, b;
  110.     //entrada del vector de adyacencias
  111.     for(int i = 0; i < m; i++)
  112.     {
  113.         cin >> a >> b;
  114.         adj[a].push_back(b);
  115.         adj[b].push_back(a);
  116.         aristas.push_back({a,b});
  117.     }
  118.     //inicialización de cada nodo desde donde comenzara el BFS
  119.     for(int i = 0; i < n; i++)
  120.         datos[i][i] = {1, 0, i};
  121.    
  122.     int nodoInicial = -1, nodoDestino = -1, nodoIntermedio = -1;
  123.     BFS(n, nodoInicial, nodoDestino, nodoIntermedio);
  124.  
  125.     if(nodoInicial == -1 && nodoDestino == -1)
  126.         mostrarCaminosMinimos(n);
  127.     else mostrarDosCaminos(nodoInicial, nodoIntermedio, nodoDestino);
  128.     return 0;
  129. }
RAW Paste Data Copied