Dada una array A que contiene N enteros, la tarea es contar el número de elementos que forman un ciclo en la array, según la siguiente condición.
Comience a recorrer el Array desde el índice i y salte al siguiente índice conectado. Un borde dirigido sale del índice i de A al índice j si j = GCD(i, A[i]) % N . Si al atravesar la array en el orden descrito, se vuelve a visitar el índice i, se dice que el índice i forma un ciclo en una array.
Ejemplos:
Entrada: A = { 1, 1, 6, 2 }
Salida: 2
Explicación:
Los recorridos posibles con la condición dada son:
0 -> 1 -> 1
1 -> 1
2 -> 2
3 -> 2 -> 2
Claramente, solo los vértices 1 y 2 forman un ciclo.
Entrada: A = {0, 0, 0, 6}
Salida: 4
Explicación:
Los recorridos posibles con la condición dada son:
0 -> 0
1 -> 1
2 -> 2
3 -> 3
Claramente, todos los vértices forman un ciclo .
Enfoque:
Para resolver el problema mencionado anteriormente, debemos suponer que cada índice representa un solo Node del gráfico .
- Cada Node tiene un único borde dirigido desde el índice i de A hasta el índice j si j = GCD(i, A[i]) % n. Si el recorrido comienza 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.
- Ahora, cada Node en este ciclo se contará ya que cada uno de ellos está formando el 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.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to number of elements
// which form a cycle in an array
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define mod 1000000007
// Function to count number of
// elements forming a cycle
int solve(int A[], int n)
{
int i, cnt = 0, j;
// Array to store parent
// node of traversal.
int parent[n];
// Array to determine
// whether current node
// is already counted
// in the cycle.
int vis[n];
// 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 = __gcd(j, A[j]) % 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 = __gcd(j, A[j]) % n;
}
}
}
}
return cnt;
}
int main()
{
int A[] = { 1, 1, 6, 2 };
int n = sizeof(A) / sizeof(A[0]);
cout << solve(A, n);
return 0;
}
Java
// Java program to number of elements
// which form a cycle in an array
import java.util.*;
class GFG{
static final int mod = 1000000007;
// Function to count number of
// elements forming a cycle
static int solve(int A[], int n)
{
int i, cnt = 0, j;
// Array to store parent
// node of traversal.
int []parent = new int[n];
// Array to determine
// whether current node
// is already counted
// in the cycle.
int []vis = new int[n];
// Initialize the arrays.
Arrays.fill(parent, -1);
Arrays.fill(vis, 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 = __gcd(j, A[j]) % 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 = __gcd(j, A[j]) % n;
}
}
}
}
return cnt;
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1, 1, 6, 2 };
int n = A.length;
System.out.print(solve(A, n));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to number of elements # which form a cycle in an array import math mod = 1000000007 # Function to count number of # elements forming a cycle def solve(A, n): cnt = 0 # Array to store parent # node of traversal. parent = [-1] * n # Array to determine # whether current node # is already counted # in the cycle. vis = [0] * n for i in range(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 = math.gcd(j, A[j]) % 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 += 1 j = math.gcd(j, A[j]) % n return cnt # Driver code A = [ 1, 1, 6, 2 ] n = len(A) print(solve(A, n)) # This code is contributed by sanjoy_62
C#
// C# program to number of elements
// which form a cycle in an array
using System;
class GFG{
// Function to count number of
// elements forming a cycle
static int solve(int[] A, int n)
{
int i, cnt = 0, j;
// Array to store parent
// node of traversal.
int[] parent = new int[n];
// Array to determine
// whether current node
// is already counted
// in the cycle.
int[] vis = new int[n];
// Initialize the arrays.
Array.Fill(parent, -1);
Array.Fill(vis, 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 = __gcd(j, A[j]) % 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 = __gcd(j, A[j]) % n;
}
}
}
}
return cnt;
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver code
static void Main()
{
int[] A = { 1, 1, 6, 2 };
int n = A.Length;
Console.WriteLine(solve(A, n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program to number of elements
// which form a cycle in an array
// Function to count number of
// elements forming a cycle
function solve(A, n)
{
let i, cnt = 0, j;
// Array to store parent
// node of traversal.
let parent = new Array(n);
// Array to determine
// whether current node
// is already counted
// in the cycle.
let vis = new Array(n);
// 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 = __gcd(j, A[j]) % 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 = __gcd(j, A[j]) % n;
}
}
}
}
return cnt;
}
function __gcd(a, b)
{
return b == 0 ? a : __gcd(b, a % b);
}
let A = [ 1, 1, 6, 2 ];
let n = A.length;
document.write(solve(A, n));
</script>
Producción:
2
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA