What's new

How do I solve the following graph problem


Active member
Staff member
The problem statement

Given a directed graph of N nodes where each node is pointing to any one of the N nodes (can possibly point to itself). Ishu, the coder, is bored and he has discovered a problem out of it to keep himself busy. Problem is as follows:

A node is 'good' if it satisfies one of the following:

  1. It is the special node (marked as node 1)
  2. It is pointing to the special node (node 1)
  3. It is pointing to a good node. Ishu is going to change pointers of some nodes to make them all 'good'. You have to find the minimum number of pointers to change in order to make all the nodes good (Thus, a Good Graph).

NOTE: Resultant Graph should hold the property that all nodes are good and each node must point to exactly one node.

Problem Constraints

1 <= N <= 10^5

Input Format

First and only argument is an integer array A containing N numbers all between 1 to N, where i-th number is the number of node that i-th node is pointing to.

Output Format

An Integer denoting minimum number of pointer changes.

My Attempted Solution

I tried building a graph by reversing the edges, and then trying to colour connected nodes, the answer would be colors - 1. In short , I was attempting to find number of connected components for a directed graph, which does not make sense(as directed graphs do not have any concept of connected components). Other solutions on the web like this and this also point out to find number of connected components, but again connected components for aa directed graph does not make any sense to me. The question looks a bit trickier to me than a first look at it suggests.

Continue reading...