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

Envío 4013

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: Juan Jr
  • Fecha: 2021-04-28 17:02:11 UTC (Hace casi 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 1 KBi
#2
Correcto
0.005 s 2 KBi
#3
Correcto
0.006 s 1 KBi
#4
Correcto
0.003 s 0 KBi
#5
Correcto
0.002 s 2 KBi
#6
Correcto
0.004 s 1 KBi
#7
Correcto
0.002 s 2 KBi
#8
Correcto
0.003 s 2 KBi
#9
Correcto
0.005 s 2 KBi
#10
Correcto
0.004 s 1 KBi
#11
Correcto
0.003 s 0 KBi
#12
Incorrecto
0.003 s 0 KBi
#13
Correcto
0.004 s 1 KBi
#14
Incorrecto
0.003 s 2 KBi
#15
Correcto
0.004 s 6 KBi
#16
Correcto
0.005 s 2 KBi
#17
Correcto
0.004 s 2 KBi
#18
Correcto
0.005 s 2 KBi
#19
Correcto
0.005 s 2 KBi
#20
Incorrecto
0.004 s 3 KBi
#21
Incorrecto
0.003 s 0 KBi
#22
Correcto
0.004 s 1 KBi
#23
Correcto
0.005 s 1 KBi
#24
Correcto
0.005 s 2 KBi
#25
Correcto
0.006 s 2 KBi
#26
Correcto
0.005 s 5 KBi
#27
Incorrecto
0.024 s 2 KBi
#28
Correcto
0.007 s 2 KBi
#29
Correcto
0.023 s 2 KBi
#30
Incorrecto
0.006 s 2 KBi
#31
Incorrecto
0.012 s 2 KBi
#32
Correcto
0.041 s 2 KBi
#33
Correcto
0.017 s 3 KBi
#34
Incorrecto
0.01 s 3 KBi
#35
Correcto
0.03 s 3 KBi
Puntos totales: 78 / 100

Código

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define sz(x) int(x.size())
#define dbg(x) cout << #x << " = " << x << endl

int n, m;
vector<vector<int>> ady;
vector<int> color;


bool dfs(int v) {
    color[v] = 1;
    for (int &u: ady[v]) {
        if (color[u] == 1) {
            return true;
        } else if (color[u] == 0) {
            return dfs(u);
        }
    }
    color[v] = 2;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    ady.resize(n);
    color.resize(n);

    while (m--) {
        int v, u; cin >> v >> u;
        ady[v].push_back(u);
    }

    bool flag = false;
    for (int i = 0; i < n; ++i) {
        if (color[i] == 0) {
            if (dfs(i)) {
                flag = true;
                break;
            }
        }
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}