Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- struct Grafo
- {
- vector <vector <int> > adj;
- vector <bool> v;
- vector <int> color;
- void leer()
- {
- int nodos, aristas;
- cin >> nodos >> aristas;
- adj.resize(nodos+1);
- v = vector <bool> (nodos+1, false);
- color = vector <int> (nodos+1, -1);
- int desde, hasta;
- for(int i=0; i<aristas; i++)
- {
- cin >> desde >> hasta;
- adj[desde].push_back(hasta);
- adj[hasta].push_back(desde);
- }
- }
- bool tieneCiclo = false;
- void DFS(int n, int p)
- {
- v[n] = true;
- for(int i=0; i<adj[n].size(); i++)
- {
- int vecino = adj[n][i];
- if(v[vecino] == false)
- {
- DFS(vecino, n);
- }
- else if(vecino != p)
- {
- tieneCiclo = true;
- }
- }
- }
- bool hayCiclo()
- {
- DFS(1, -1);
- return tieneCiclo;
- }
- ///TAREA: HACER BICOLOREO CON DFS
- bool esBicoloreable(int n)
- {
- bool valor1 = true;
- bool valor2 = !valor1; ///esto vale false
- bool valor3 = !valor2; ///esto vale true
- color[n] = 0;
- queue <int> cola;
- cola.push(n);
- while(cola.size() > 0)
- {
- int nodo = cola.front();
- cola.pop();
- for(int i=0; i<adj[nodo].size(); i++)
- {
- int vecino = adj[nodo][i];
- if(color[vecino] == color[nodo]) ///Si ya tiene color asignado
- {
- return false; ///No se puede bicolorear
- }
- else
- {
- color[vecino] = !color[nodo];
- cola.push(vecino);
- }
- }
- }
- return true;
- }
- };
- int main()
- {
- Grafo g;
- g.leer();
- cout << g.hayCiclo() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment