Dada una array A de enteros. Se dice que el índice i de A está conectado al índice j si j = (i + A[i]) % n + 1 (suponga una indexación basada en 1). Comience a atravesar la array desde el índice i y salte a su siguiente índice conectado. Si al atravesar la array en el orden descrito, se vuelve a visitar el índice i, entonces el índice i es un índice mágico. Cuente el número de índices mágicos en la array. Suponga que la array A consta de enteros no negativos.
Ejemplos:
Input : A = {1, 1, 1, 1}
Output : 4
Possible traversals:
1 -> 3 -> 1
2 -> 4 -> 2
3 -> 1 -> 3
4 -> 2 -> 4
Clearly all the indices are magical
Input : A = {0, 0, 0, 2}
Output : 2
Possible traversals:
1 -> 2 -> 3 -> 4 -> 3...
2 -> 3 -> 4 -> 3...
3 -> 4 -> 3
4 -> 3 ->4
Magical indices = 3, 4
Enfoque: El problema es contar el número de Nodes en todos los ciclos presentes en el gráfico. Cada índice representa un solo Node del gráfico. Cada Node tiene un solo borde dirigido como se describe en el enunciado del problema. Este grafo tiene una propiedad especial: al iniciar un recorrido desde cualquier vértice, siempre se detecta un ciclo. Esta propiedad será útil para reducir la complejidad temporal de la solución.
Lea esta publicación sobre cómo detectar el ciclo en un gráfico dirigido: Detectar ciclo en un gráfico dirigido
Deje que el recorrido comience desde el Node i. El Node i se llamará Node principal de este recorrido y este Node principal se asignará a todos los Nodes visitados durante el recorrido. Mientras recorremos el gráfico, si descubrimos un Node que ya ha sido visitado y el Node principal de ese Node visitado es el mismo que el Node principal del recorrido, entonces se detecta un nuevo ciclo. Para contar el número de Nodes en este ciclo, inicie otro dfs desde este Node hasta que no se vuelva a visitar este mismo Node. Este procedimiento se repite para cada Node i del gráfico. En el peor de los casos, cada Node se recorrerá como máximo 3 veces. Por lo tanto, la solución tiene una complejidad de tiempo lineal.
El algoritmo paso a paso es:
1. For each node in the graph:
if node i is not visited then:
for every adjacent node j:
if node j is not visited:
par[j] = i
else:
if par[j]==i
cycle detected
count nodes in cycle
2. return count
Implementación:
C++
// C++ program to find number of magical
// indices in the given array.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define mod 1000000007
// Function to count number of magical indices.
int solve(int A[], int n)
{
int i, cnt = 0, j;
// Array to store parent node of traversal.
int parent[n + 1];
// Array to determine whether current node
// is already counted in the cycle.
int vis[n + 1];
// Initialize the arrays.
memset(parent, -1, sizeof(parent));
memset(vis, 0, sizeof(vis));
for (i = 0; i < n; i++) {
j = i;
// Check if current node is already
// traversed or not. If node is not
// traversed yet then parent value
// will be -1.
if (parent[j] == -1) {
// Traverse the graph until an
// already visited node is not
// found.
while (parent[j] == -1) {
parent[j] = i;
j = (j + A[j] + 1) % n;
}
// Check parent value to ensure
// a cycle is present.
if (parent[j] == i) {
// Count number of nodes in
// the cycle.
while (!vis[j]) {
vis[j] = 1;
cnt++;
j = (j + A[j] + 1) % n;
}
}
}
}
return cnt;
}
int main()
{
int A[] = { 0, 0, 0, 2 };
int n = sizeof(A) / sizeof(A[0]);
cout << solve(A, n);
return 0;
}
Java
// Java program to find number of magical
// indices in the given array.
import java.io.*;
import java.util.*;
public class GFG {
// Function to count number of magical
// indices.
static int solve(int []A, int n)
{
int i, cnt = 0, j;
// Array to store parent node of
// traversal.
int []parent = new int[n + 1];
// Array to determine whether current node
// is already counted in the cycle.
int []vis = new int[n + 1];
// Initialize the arrays.
for (i = 0; i < n+1; i++) {
parent[i] = -1;
vis[i] = 0;
}
for (i = 0; i < n; i++) {
j = i;
// Check if current node is already
// traversed or not. If node is not
// traversed yet then parent value
// will be -1.
if (parent[j] == -1) {
// Traverse the graph until an
// already visited node is not
// found.
while (parent[j] == -1) {
parent[j] = i;
j = (j + A[j] + 1) % n;
}
// Check parent value to ensure
// a cycle is present.
if (parent[j] == i) {
// Count number of nodes in
// the cycle.
while (vis[j]==0) {
vis[j] = 1;
cnt++;
j = (j + A[j] + 1) % n;
}
}
}
}
return cnt;
}
// Driver code
public static void main(String args[])
{
int []A = { 0, 0, 0, 2 };
int n = A.length;
System.out.print(solve(A, n));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
Python3
# Python3 program to find number of magical # indices in the given array. # Function to count number of magical # indices. def solve(A, n) : cnt = 0 # Array to store parent node of # traversal. parent = [None] * (n + 1) # Array to determine whether current node # is already counted in the cycle. vis = [None] * (n + 1) # Initialize the arrays. for i in range(0, n+1): parent[i] = -1 vis[i] = 0 for i in range(0, n): j = i # Check if current node is already # traversed or not. If node is not # traversed yet then parent value # will be -1. if (parent[j] == -1) : # Traverse the graph until an # already visited node is not # found. while (parent[j] == -1) : parent[j] = i j = (j + A[j] + 1) % n # Check parent value to ensure # a cycle is present. if (parent[j] == i) : # Count number of nodes in # the cycle. while (vis[j]==0) : vis[j] = 1 cnt = cnt + 1 j = (j + A[j] + 1) % n return cnt # Driver code A = [ 0, 0, 0, 2 ] n = len(A) print (solve(A, n)) # This code is contributed by Manish Shaw # (manishshaw1)
C#
// C# program to find number of magical
// indices in the given array.
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function to count number of magical
// indices.
static int solve(int []A, int n)
{
int i, cnt = 0, j;
// Array to store parent node of
// traversal.
int []parent = new int[n + 1];
// Array to determine whether current node
// is already counted in the cycle.
int []vis = new int[n + 1];
// Initialize the arrays.
for (i = 0; i < n+1; i++) {
parent[i] = -1;
vis[i] = 0;
}
for (i = 0; i < n; i++) {
j = i;
// Check if current node is already
// traversed or not. If node is not
// traversed yet then parent value
// will be -1.
if (parent[j] == -1) {
// Traverse the graph until an
// already visited node is not
// found.
while (parent[j] == -1) {
parent[j] = i;
j = (j + A[j] + 1) % n;
}
// Check parent value to ensure
// a cycle is present.
if (parent[j] == i) {
// Count number of nodes in
// the cycle.
while (vis[j]==0) {
vis[j] = 1;
cnt++;
j = (j + A[j] + 1) % n;
}
}
}
}
return cnt;
}
// Driver code
public static void Main()
{
int []A = { 0, 0, 0, 2 };
int n = A.Length;
Console.WriteLine(solve(A, n));
}
}
// This code is contributed by Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to find
// number of magical
// indices in the given
// array.
// Function to count number
// of magical indices.
function solve($A, $n)
{
$i = 0;
$cnt = 0;
$j = 0;
// Array to store parent
// node of traversal.
$parent = array();
// Array to determine
// whether current node
// is already counted
// in the cycle.
$vis = array();
// Initialize the arrays.
for ($i = 0; $i < $n + 1; $i++)
{
$parent[$i] = -1;
$vis[$i] = 0;
}
for ($i = 0; $i < $n; $i++)
{
$j = $i;
// Check if current node is
// already traversed or not.
// If node is not traversed
// yet then parent value will
// be -1.
if ($parent[$j] == -1)
{
// Traverse the graph until
// an already visited node
// is not found.
while ($parent[$j] == -1)
{
$parent[$j] = $i;
$j = ($j + $A[$j] + 1) % $n;
}
// Check parent value to ensure
// a cycle is present.
if ($parent[$j] == $i)
{
// Count number of
// nodes in the cycle.
while ($vis[$j] == 0)
{
$vis[$j] = 1;
$cnt++;
$j = ($j + $A[$j] + 1) % $n;
}
}
}
}
return $cnt;
}
// Driver code
$A = array( 0, 0, 0, 2 );
$n = count($A);
echo (solve($A, $n));
// This code is contributed by
// Manish Shaw (manishshaw1)
?>
Javascript
<script>
// Javascript program to find number of magical
// indices in the given array.
mod = 1000000007
// Function to count number of magical indices.
function solve(A, n)
{
var i, cnt = 0, j;
// Array to store parent node of traversal.
var parent = new Array(n + 1);
// Array to determine whether current node
// is already counted in the cycle.
var vis = new Array(n + 1);
// Initialize the arrays.
parent.fill(-1);
vis.fill(0);
for(i = 0; i < n; i++)
{
j = i;
// Check if current node is already
// traversed or not. If node is not
// traversed yet then parent value
// will be -1.
if (parent[j] == -1)
{
// Traverse the graph until an
// already visited node is not
// found.
while (parent[j] == -1)
{
parent[j] = i;
j = (j + A[j] + 1) % n;
}
// Check parent value to ensure
// a cycle is present.
if (parent[j] == i)
{
// Count number of nodes in
// the cycle.
while (!vis[j])
{
vis[j] = 1;
cnt++;
j = (j + A[j] + 1) % n;
}
}
}
}
return cnt;
}
// Driver code
var A = [ 0, 0, 0, 2 ];
var n = A.length;
document.write(solve(A, n));
// This code is contributed by SoumikMondal
</script>
Producción :
2
Complejidad temporal: O(n)
Complejidad espacial: O(n)