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

Envío 2554

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: judavid.arias
  • Fecha: 2021-01-03 16:13:35 UTC (Hace casi 2 años)
Caso # Resultado Tiempo Memoria
#1
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.096 s 11 KBi
#2
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.117 s 14 KBi
#3
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.118 s 11 KBi
#4
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.099 s 11 KBi
#5
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.123 s 14 KBi
#6
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.099 s 14 KBi
#7
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.123 s 11 KBi
#8
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.119 s 14 KBi
#9
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.102 s 11 KBi
#10
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.112 s 14 KBi
#11
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.089 s 11 KBi
#12
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.11 s 11 KBi
#13
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.099 s 14 KBi
#14
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.117 s 14 KBi
#15
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.095 s 11 KBi
#16
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.1 s 14 KBi
#17
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.102 s 14 KBi
#18
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.097 s 15 KBi
#19
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.115 s 11 KBi
#20
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.127 s 11 KBi
#21
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.103 s 14 KBi
#22
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.097 s 11 KBi
#23
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.099 s 11 KBi
#24
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.112 s 15 KBi
#25
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.11 s 14 KBi
#26
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.09 s 14 KBi
#27
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.11 s 15 KBi
#28
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.107 s 14 KBi
#29
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.119 s 15 KBi
#30
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.109 s 14 KBi
#31
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.09 s 14 KBi
#32
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.111 s 15 KBi
#33
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.094 s 14 KBi
#34
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.091 s 14 KBi
#35
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Error: Could not find or load main class Main
Caused by: java.lang.NoClassDefFoundError: com/company/Main (wrong name: Main)
0.104 s 14 KBi
Puntos totales: 0 / 100

Código

package com.company;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main{

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }



    private static List<List<Integer>> adj = new ArrayList<>();
    private static Integer V;

    private static void addEdge(int u , int v){
        adj.get(u).add(v);
    }

    static boolean isCycle(int u, boolean[] visited, Stack<Integer> rec){
        if(!visited[u]){
            visited[u] = true;
            rec.push(u);

            List<Integer> ajds = adj.get(u);
            for (Integer v :  ajds) {
                if(!visited[v] && isCycle(v, visited,rec))
                    return true;
                else if (rec.contains(v))
                    return true;
            }
        }
        if(!rec.empty())
            rec.pop();
        return false;
    }

    private static boolean isCycle(){

        boolean[] visited = new boolean[V];


        for (int i = 0; i < V; i++) {
            if(isCycle(i, visited, new Stack<Integer>()))
                return true;
        }
        return false;

    }

    public static void main(String[] args) throws IOException {
        Reader sc = new Reader();
        V = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            addEdge(sc.nextInt(), sc.nextInt());
        }

        System.out.println(isCycle() ? "Yes" : "No");


    }


}