Total number of components in the index Array

0 0 9 minutes read

Given an array arr[] of N integers of value from 0 to N, the task is to count the number of components in Index Array.

Index array means if we are at ith index then it leads to arr[i].
The component of an index array is counted when it forms a cycle. If no cycle persists or the array contains a single element then also we consider it as a component.
For Example:
Let array arr[] = {1, 2, 0, 3}
{1, 2, 0} will form one component as starting from index 0 we reach the index 0 again as:
1 -> 2(arr[1]) -> 0(arr[2]) -> 1(arr[0])

Examples:

Input: arr[] = {1, 2, 3, 5, 0, 4, 6}
Output: 2
Explanation:
Below is the traversal of the 2 components:
Component 1: Start traversal from 0, then the path of traversal is given by:
1 -> 2(arr[1]) -> 3(arr[2]) -> 5(arr[3]) -> 4(arr[5]) -> 0(arr[4]) -> 1(arr[0]).
Component 2: Only 6 is unvisited it creates one more component.
So, the total components = 2.

Input: arr[] = {1, 2, 0, 3}
Output: 2
Explanation:
Below is the traversal of the 2 components:
Component 1: Start traversal from 0, then the path of traversal is given by:
1 -> 2(arr[1]) -> 0(arr[2]) -> 1(arr[0])
Component 2: Only 3 is unvisited it creates one more component.
So, the total components = 2.

Approach: The idea is to use the concept of DFS traversal. Below are the steps:

Start from the first unvisited index which will be index with integer 0 in it.
During DFS Traversal mark the visited elements in the array until the elements form a cycle.
If a cycle is formed then it means that we have got one component and hence increase the component count.
Repeat all the above steps for all the unvisited index in the array and count the total components in the given index array.
If all the index of the array are visited, then print the total count of connected components.

Below is the implementation of the above approach:

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
    // recur 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
        // recur 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
    # recur 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
    // recur 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
    // recur 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>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach: Union-Find

The Union-Find, also known as the Disjoint-Set data structure, is a data structure and algorithm used to efficiently perform operations on disjoint sets of elements. It provides two main operations find and union.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
 
#include <iostream>
#include <vector>
 
using namespace std;
 
// Find operation to determine the representative element of
// a set
int find(vector<int>& parent, int i)
{
    if (parent[i] == i)
        return i;
    return find(parent, parent[i]);
}
 
// Union operation to merge two sets
void unionSet(vector<int>& parent, int i, int j)
{
    int rootA = find(parent, i);
    int rootB = find(parent, j);
    if (rootA != rootB)
        parent[rootA] = rootB;
}
 
int countComponents(vector<int>& arr)
{
    int N = arr.size();
    vector<int> parent(N);
 
    // Initialize parent array
    for (int i = 0; i < N; i++)
        parent[i] = i;
 
    // Initialize with N components
    int componentCount = N;
    // Iterate through each index
    for (int i = 0; i < N; i++) {
        int rootA = find(parent, i);
        int rootB = find(parent, arr[i]);
        if (rootA != rootB) {
            unionSet(parent, rootA, rootB);
            componentCount--;
        }
    }
    // Return the count of components
    return componentCount;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 2, 3, 5, 0, 4, 6 };
    int result = countComponents(arr);
    cout << result << endl;
    return 0;
}

Java

import java.io.*;
import java.util.Arrays;
 
class Main {
    // Find operation to determine the representative element of
    //a set
    static int find(int[] parent, int i) {
        if (parent[i] == i)
            return i;
        return find(parent, parent[i]);
    }
    // Union operation to merge two sets
    static void unionSet(int[] parent, int i, int j) {
        int rootA = find(parent, i);
        int rootB = find(parent, j);
        if (rootA != rootB)
            parent[rootA] = rootB;
    }
    static int countComponents(int[] arr) {
        int N = arr.length;
        int[] parent = new int[N];
        // Initialize parent array
        for (int i = 0; i < N; i++)
            parent[i] = i;
        // Initialize with N components
        int componentCount = N;
        // Iterate through each index
        for (int i = 0; i < N; i++) {
            int rootA = find(parent, i);
            int rootB = find(parent, arr[i]);
            if (rootA != rootB) {
                unionSet(parent, rootA, rootB);
                componentCount--;
            }
        }
        // Return the count of components
        return componentCount;
    }
    // Driver Code
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 5, 0, 4, 6 };
        int result = countComponents(arr);
        System.out.println(result);
    }
}

Python

def GFG(parent, i):
    if parent[i] == i:
        return i
    return GFG(parent, parent[i])
# Union operation to 
# merge two sets
def union_set(parent, i, j):
    root_a = GFG(parent, i)
    root_b = GFG(parent, j)
    if root_a != root_b:
        parent[root_a] = root_b
def count_components(arr):
    N = len(arr)
    parent = list(range(N)) 
    # Initialize parent array
    component_count = N  
    # Initialize with N components
    for i in range(N):
        root_a = GFG(parent, i)
        root_b = GFG(parent, arr[i])
        if root_a != root_b:
            union_set(parent, root_a, root_b)
            component_count -= 1
    return component_count
# Driver Code
if __name__ == "__main__":
    arr = [1, 2, 3, 5, 0, 4, 6]
    result = count_components(arr)
    print(result)

C#

using System;
using System.Collections.Generic;
 
public class MainClass
{
    // Find operation to determine the representative element of a set
    public static int Find(List<int> parent, int i)
    {
        if (parent[i] == i)
            return i;
        return Find(parent, parent[i]);
    }
 
    // Union operation to merge two sets
    public static void UnionSet(List<int> parent, int i, int j)
    {
        int rootA = Find(parent, i);
        int rootB = Find(parent, j);
        if (rootA != rootB)
            parent[rootA] = rootB;
    }
 
    public static int CountComponents(List<int> arr)
    {
        int N = arr.Count;
        List<int> parent = new List<int>(N);
 
        // Initialize parent array
        for (int i = 0; i < N; i++)
            parent.Add(i);
 
        // Initialize with N components
        int componentCount = N;
        // Iterate through each index
        for (int i = 0; i < N; i++)
        {
            int rootA = Find(parent, i);
            int rootB = Find(parent, arr[i]);
            if (rootA != rootB)
            {
                UnionSet(parent, rootA, rootB);
                componentCount--;
            }
        }
        // Return the count of components
        return componentCount;
    }
 
    public static void Main(string[] args)
    {
        List<int> arr = new List<int> { 1, 2, 3, 5, 0, 4, 6 };
        int result = CountComponents(arr);
        Console.WriteLine(result);
    }
}

Javascript

// Find operation to determine the representative element of a set
function find(parent, i) {
    if (parent[i] === i) {
        return i;
    }
    return find(parent, parent[i]);
}
 
// Union operation to merge two sets
function unionSet(parent, i, j) {
    const rootA = find(parent, i);
    const rootB = find(parent, j);
    if (rootA !== rootB) {
        parent[rootA] = rootB;
    }
}
 
// Function to count the number of connected components
function countComponents(arr) {
    const N = arr.length;
    const parent = new Array(N);
 
    // Initialize parent array
    for (let i = 0; i < N; i++) {
        parent[i] = i;
    }
 
    let componentCount = N;
 
    // Iterate through each index
    for (let i = 0; i < N; i++) {
        const rootA = find(parent, i);
        const rootB = find(parent, arr[i]);
        if (rootA !== rootB) {
            unionSet(parent, rootA, rootB);
            componentCount--;
        }
    }
     
    // Return the count of components
    return componentCount;
}
 
// Example array of connections
const arr = [1, 2, 3, 5, 0, 4, 6];
const result = countComponents(arr);
console.log(result);

Output

Time Complexity: O(N), where N is the size of the input array
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!