█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 3960

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: ppastram
  • Fecha: 2021-04-25 03:31:56 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 1 KBi
#2
Correcto
0.004 s 2 KBi
#3
Correcto
0.003 s 2 KBi
#4
Correcto
0.004 s 1 KBi
#5
Correcto
0.005 s 2 KBi
#6
Correcto
0.003 s 2 KBi
#7
Correcto
0.004 s 1 KBi
#8
Correcto
0.003 s 2 KBi
#9
Correcto
0.004 s 1 KBi
#10
Correcto
0.004 s 55 KBi
#11
Correcto
0.005 s 5 KBi
#12
Correcto
0.005 s 25 KBi
#13
Correcto
0.004 s 40 KBi
#14
Correcto
0.004 s 2 KBi
#15
Correcto
0.005 s 3 KBi
#16
Correcto
0.004 s 1 KBi
#17
Correcto
0.006 s 2 KBi
#18
Correcto
0.004 s 1 KBi
#19
Correcto
0.003 s 2 KBi
#20
Correcto
0.005 s 2 KBi
#21
Correcto
0.003 s 2 KBi
#22
Correcto
0.005 s 26 KBi
#23
Correcto
0.004 s 1 KBi
#24
Correcto
0.005 s 3 KBi
#25
Correcto
0.003 s 2 KBi
#26
Correcto
0.009 s 12 KBi
#27
Correcto
0.025 s 3 KBi
#28
Correcto
0.008 s 13 KBi
#29
Correcto
0.04 s 3 KBi
#30
Correcto
0.008 s 2 KBi
#31
Correcto
0.007 s 2 KBi
#32
Correcto
0.033 s 3 KBi
#33
Correcto
0.015 s 3 KBi
#34
Correcto
0.015 s 2 KBi
#35
Correcto
0.038 s 3 KBi
Puntos totales: 100 / 100

Código

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#define forn(a, n) for(int a = 0; a<(int) (n); ++a)
#define rforn(a, n) for(int a = (n)-1; a>=0; --a)
using namespace std;
const int N = 6e5+20;

bool visitados [10000] = {false};
bool visitando [10000] = {false};
vector < vector<int> > ady;
bool ciclo = false;

void DFS(int x)
{
    visitando[x] = true;
    for(int i = 0; i < ady[x].size(); i++)
    {
        if (visitando[ady[x][i]])
            ciclo = true;
        else if(!visitados[ady[x][i]])
            DFS(ady[x][i]);
    }
    visitados[x] = true;
    visitando[x] = false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int nodos;
    int aristas;
    int desde;
    int hasta;
    int este;
    string res = "No";
    cin>>nodos>>aristas;
    
    for(int k = 0; k < nodos; k++)
    {
        vector<int> vacia;
        ady.push_back(vacia);
    }
    for(int k = 0; k < aristas; k++)
    {
        cin>>desde>>hasta;
        ady[desde].push_back(hasta);
    }
    /*for(int k = 0; k < aristas; k++)
    {
        for(int i = 0; i < ady[k].size(); i++) cout<<ady[k][i]<<" - ";
        cout<<endl;
    }*/
    ///
    for(int k = 0; k < nodos; k++)
    {
        DFS(k);
    }
    if(ciclo) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}