Envío 2553

Problema 0x53 - Encontrar ciclos en un grafo dirigido

Autor: judavid.arias
Fecha: 2021-01-03 16:12:41 UTC (Hace más de 3 años)

Caso #	Resultado	Tiempo	Memoria
#1	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#2	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#3	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#4	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#5	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#6	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#7	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#8	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#9	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#10	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#11	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#12	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#13	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#14	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#15	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#16	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#17	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#18	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#19	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#20	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#21	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#22	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#23	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#24	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#25	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#26	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#27	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#28	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#29	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#30	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#31	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#32	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#33	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#34	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors
#35	Error de compilación Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ Main.java:158: error: package Main1 does not exist Main1.Reader sc = new Main1.Reader(); ^ 2 errors

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 {
        Main1.Reader sc = new Main1.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");


    }


}