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

Envío 6015

Problema 0x53 - Encontrar ciclos en un grafo dirigido

  • Autor: jarangolp
  • Fecha: 2022-05-02 14:02:21 UTC (Hace casi 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.057 s 8 KBi
#2
Incorrecto
0.026 s 6 KBi
#3
Correcto
0.052 s 7 KBi
#4
Incorrecto
0.024 s 6 KBi
#5
Incorrecto
0.047 s 6 KBi
#6
Correcto
0.059 s 6 KBi
#7
Incorrecto
0.026 s 6 KBi
#8
Incorrecto
0.023 s 6 KBi
#9
Incorrecto
0.02 s 6 KBi
#10
Incorrecto
0.096 s 27 KBi
#11
Incorrecto
0.073 s 32 KBi
#12
Incorrecto
0.093 s 8 KBi
#13
Incorrecto
0.026 s 7 KBi
#14
Correcto
0.06 s 13 KBi
#15
Correcto
0.025 s 6 KBi
#16
Correcto
0.026 s 6 KBi
#17
Correcto
0.018 s 6 KBi
#18
Incorrecto
0.019 s 6 KBi
#19
Incorrecto
0.075 s 31 KBi
#20
Incorrecto
0.081 s 10 KBi
#21
Incorrecto
0.024 s 6 KBi
#22
Correcto
0.053 s 6 KBi
#23
Correcto
0.061 s 6 KBi
#24
Correcto
0.024 s 7 KBi
#25
Correcto
0.086 s 7 KBi
#26
Correcto
0.023 s 6 KBi
#27
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.036 s 10 KBi
#28
Correcto
0.054 s 8 KBi
#29
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.075 s 13 KBi
#30
Correcto
0.021 s 7 KBi
#31
Correcto
0.033 s 9 KBi
#32
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.032 s 10 KBi
#33
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.035 s 11 KBi
#34
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.026 s 11 KBi
#35
Error en tiempo de ejecución (NZEC)
Exited with error status 1
/box/script.js:24
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
                               ^

TypeError: Cannot read property 'split' of undefined
    at ReadStream.<anonymous> (/box/script.js:24:32)
    at ReadStream.emit (events.js:210:5)
    at addChunk (_stream_readable.js:309:12)
    at readableAddChunk (_stream_readable.js:290:11)
    at ReadStream.Readable.push (_stream_readable.js:224:10)
    at internal/fs/streams.js:191:12
    at FSReqCallback.wrapper [as oncomplete] (fs.js:470:5)
0.033 s 10 KBi
Puntos totales: 43 / 100

Código

const adj = new Map();
let visited = [], disc = [], low =[], ans = [];

function dfs(index, parent=null, time=1) {
  visited[index] = true;
  disc[index] = time;
  low[index] = time;
  adj[index] = adj[index] || [];
  for (let neighbor of adj[index]) {
    if (neighbor === parent) continue;
    if (!visited[neighbor]) dfs(neighbor, index, time+1);
    low[index] = Math.min(low[index], low[neighbor]);
    if (low[neighbor] > disc[index]) {
      ans.push([index, neighbor]);
    }
  }
}

process.stdin.on('data', data => {
  const dataArray = data.toString().split('\n');
  if (dataArray.length === 0) return;
  const [N, M] = dataArray[0].split(' ').map(n => Number(n));
  for (let i = 1; i < M; i++) {
    const [u,v] = dataArray[i].split(' ').map(n => Number(n));
    adj[u] = adj[u] || [];
    adj[u].push(v);
  }
  visited = new Array(N).fill(false);
  dfs(0);
  const resp = ans.length > 0 ? 'Yes' : 'No';
  console.log(resp)
})