Dada una array arr[] de N enteros de valor de 0 a N , la tarea es contar el número de componentes en Index Array.
La array de índice significa que si estamos en el i-ésimo índice, entonces conduce a arr[i].
El componente de una array de índice se cuenta cuando forma un ciclo. Si no persiste ningún ciclo o la array contiene un solo elemento, también lo consideramos como un componente.
Por ejemplo:
Let array arr[] = {1, 2, 0, 3}
{1, 2, 0} formará un componente ya que comenzando desde el índice 0 alcanzamos el índice 0 nuevamente como:
1 -> 2 (arr[1 ]) -> 0(arr[2]) -> 1(arr[0])
Ejemplos:
Entrada: arr[] = {1, 2, 3, 5, 0, 4, 6}
Salida: 2
Explicación:
A continuación se muestra el recorrido de los 2 componentes:
Componente 1: Comience el recorrido desde 0, luego se proporciona la ruta del recorrido por:
1 -> 2(arr[1]) -> 3(arr[2]) -> 5(arr[3]) -> 4(arr[5]) -> 0(arr[4]) -> 1(arr[0]).
Componente 2: solo 6 no se visitan, crea un componente más.
Entonces, los componentes totales = 2.Entrada: arr[] = {1, 2, 0, 3}
Salida: 2
Explicación:
A continuación se muestra el recorrido de los 2 componentes:
Componente 1: Comience el recorrido desde 0, luego la ruta del recorrido está dada por:
1 -> 2 (arr[1]) -> 0(arr[2]) -> 1(arr[0])
Componente 2: solo 3 no se visita, crea un componente más.
Entonces, los componentes totales = 2.
Enfoque: La idea es utilizar el concepto de recorrido DFS . A continuación se muestran los pasos:
- Comience desde el primer índice no visitado que será un índice con el número entero 0.
- Durante DFS Traversal marque los elementos visitados en la array hasta que los elementos formen un ciclo.
- Si se forma un ciclo, significa que tenemos un componente y, por lo tanto, aumentamos el recuento de componentes.
- Repita todos los pasos anteriores para todos los índices no visitados en la array y cuente los componentes totales en la array de índice dada.
- Si se visita todo el índice de la array, imprima el recuento total de componentes conectados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// To mark the visited index
// during DFS Traversal
vector<int> visited;
// Function for DFS traversal
void dfs(int i, int a[])
{
// Check if not visited then
// recurr for the next index
if (visited[i] == 0) {
visited[i] = 1;
// DFS Traversal for next index
dfs(a[i], a);
}
return;
}
// Function for checking which
// indexes are remaining
int allvisited(int a[], int n)
{
for (int i = 0; i < n; i++) {
// Marks that the ith
// index is not visited
if (visited[i] == 0)
return i;
}
return -1;
}
// Function for counting components
int count(int a[], int n)
{
int c = 0;
// Function call
int x = allvisited(a, n);
while (x != -1) {
// Count number of components
c++;
// DFS call
dfs(x, a);
x = allvisited(a, n);
}
// Print the total count of components
cout << c << endl;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 4, 3, 5, 0, 2, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
visited = vector<int>(N+1,0);
// Function Call
count(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class Main
{
// Function for DFS traversal
static void dfs(int i, int[] a,
HashMap<Integer, Integer> m)
{
// Check if not visited then
// recurr for the next index
if (!m.containsKey(i))
{
m.put(i, 1);
// DFS Traversal for next index
dfs(a[i], a, m);
}
return;
}
// Function for checking which
// indexes are remaining
static int allvisited(int[] a, int n,
HashMap<Integer, Integer> m)
{
for(int i = 0; i < n; i++)
{
// Marks that the ith
// index is not visited
if (!m.containsKey(i))
return i;
}
return -1;
}
// Function for counting components
static void count(int[] a, int n)
{
int c = 0;
// To mark the visited index
// during DFS Traversal
HashMap<Integer, Integer> m = new HashMap<>();
// Function call
int x = allvisited(a, n, m);
while (x != -1)
{
// Count number of components
c++;
// DFS call
dfs(x, a, m);
x = allvisited(a, n, m);
}
// Print the total count of components
System.out.print(c);
}
public static void main(String[] args)
{
// Given array arr[]
int[] arr = { 1, 4, 3, 5, 0, 2, 6 };
int N = arr.length;
// Function Call
count(arr, N);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program for the above approach # Function for DFS traversal def dfs(i, a, m): # Check if not visited then # recurr for the next index if i in m: if m[i] == 0: m[i] = 1 # DFS Traversal for next index dfs(a[i], a, m) else: m[i] = 1 # DFS Traversal for next index dfs(a[i], a, m) return # Function for checking which # indexes are remaining def allvisited(a, n, m): for i in range(n): # Marks that the ith # index is not visited if i in m: if m[i] == 0: return i else: return i return -1 # Function for counting components def count(a, n): c = 0 # To mark the visited index # during DFS Traversal m = dict() # Function call x = allvisited(a, n, m) while (x != -1): # Count number of components c += 1 # DFS call dfs(x, a, m) x = allvisited(a, n, m) # Print the total count of components print(c) # Driver Code if __name__=='__main__': # Given array arr[] arr = [ 1, 4, 3, 5, 0, 2, 6 ] N = len(arr) # Function Call count(arr, N) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function for DFS traversal
static void dfs(int i, int []a,
Dictionary<int, int> m)
{
// Check if not visited then
// recurr for the next index
if (!m.ContainsKey(i))
{
m[i] = 1;
// DFS Traversal for next index
dfs(a[i], a, m);
}
return;
}
// Function for checking which
// indexes are remaining
static int allvisited(int []a, int n,
Dictionary<int, int> m)
{
for(int i = 0; i < n; i++)
{
// Marks that the ith
// index is not visited
if (!m.ContainsKey(i))
return i;
}
return -1;
}
// Function for counting components
static void count(int []a, int n)
{
int c = 0;
// To mark the visited index
// during DFS Traversal
Dictionary<int,
int> m = new Dictionary<int,
int>();
// Function call
int x = allvisited(a, n, m);
while (x != -1)
{
// Count number of components
c++;
// DFS call
dfs(x, a, m);
x = allvisited(a, n, m);
}
// Print the total count of components
Console.Write(c);
}
// Driver Code
public static void Main()
{
// Given array arr[]
int []arr = { 1, 4, 3, 5, 0, 2, 6 };
int N = arr.Length;
// Function Call
count(arr, N);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript program for the above approach
// Function for DFS traversal
function dfs(i, a, m)
{
// Check if not visited then
// recurr for the next index
if (!m.has(i)) {
m.set(i, 1);
m[i] = 1;
// DFS Traversal for next index
dfs(a[i], a, m);
}
return;
}
// Function for checking which
// indexes are remaining
function allvisited(a, n, m)
{
for (var i = 0; i < n; i++) {
// Marks that the ith
// index is not visited
if (!m.has(i))
return i;
}
return -1;
}
// Function for counting components
function count(a, n)
{
var c = 0;
// To mark the visited index
// during DFS Traversal
var m = new Map();
// Function call
var x = allvisited(a, n, m);
while (x != -1) {
// Count number of components
c++;
// DFS call
dfs(x, a, m);
x = allvisited(a, n, m);
}
// Print the total count of components
document.write( c );
}
// Driver Code
// Given array arr[]
var arr = [1, 4, 3, 5, 0, 2, 6];
var N = arr.length;
// Function Call
count(arr, N);
// This code is contributed by itsok.
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA