GastonFontenla

Untitled

May 29th, 2017
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. struct Grafo
  8. {
  9.     vector <vector <int> > adj;
  10.     vector <bool> v;
  11.     vector <int> color;
  12.  
  13.     void leer()
  14.     {
  15.         int nodos, aristas;
  16.         cin >> nodos >> aristas;
  17.  
  18.         adj.resize(nodos+1);
  19.         v = vector <bool> (nodos+1, false);
  20.         color = vector <int> (nodos+1, -1);
  21.  
  22.         int desde, hasta;
  23.  
  24.         for(int i=0; i<aristas; i++)
  25.         {
  26.             cin >> desde >> hasta;
  27.             adj[desde].push_back(hasta);
  28.             adj[hasta].push_back(desde);
  29.         }
  30.     }
  31.  
  32.     bool tieneCiclo = false;
  33.  
  34.     void DFS(int n, int p)
  35.     {
  36.         v[n] = true;
  37.         for(int i=0; i<adj[n].size(); i++)
  38.         {
  39.             int vecino = adj[n][i];
  40.  
  41.             if(v[vecino] == false)
  42.             {
  43.                 DFS(vecino, n);
  44.             }
  45.             else if(vecino != p)
  46.             {
  47.                 tieneCiclo = true;
  48.             }
  49.         }
  50.     }
  51.  
  52.     bool hayCiclo()
  53.     {
  54.         DFS(1, -1);
  55.         return tieneCiclo;
  56.     }
  57.  
  58.     ///TAREA: HACER BICOLOREO CON DFS
  59.  
  60.     bool esBicoloreable(int n)
  61.     {
  62.  
  63.         bool valor1 = true;
  64.         bool valor2 = !valor1; ///esto vale false
  65.         bool valor3 = !valor2; ///esto vale true
  66.  
  67.         color[n] = 0;
  68.         queue <int> cola;
  69.         cola.push(n);
  70.  
  71.         while(cola.size() > 0)
  72.         {
  73.             int nodo = cola.front();
  74.             cola.pop();
  75.  
  76.             for(int i=0; i<adj[nodo].size(); i++)
  77.             {
  78.                 int vecino = adj[nodo][i];
  79.  
  80.                 if(color[vecino] == color[nodo]) ///Si ya tiene color asignado
  81.                 {
  82.                     return false; ///No se puede bicolorear
  83.                 }
  84.                 else
  85.                 {
  86.                     color[vecino] = !color[nodo];
  87.                     cola.push(vecino);
  88.                 }
  89.             }
  90.         }
  91.         return true;
  92.     }
  93.  
  94. };
  95.  
  96. int main()
  97. {
  98.     Grafo g;
  99.     g.leer();
  100.  
  101.     cout << g.hayCiclo() << endl;
  102.  
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment