Interview Question, Help needed

general
1

We have a list of N nodes with each node pointing to one of the N nodes.
It could even be pointing to itself. We call a node ‘good’,
if it satisfies one of the following properties:

  • It is the tail node (marked as node 1)
  • It is pointing to the tail node (node 1)
  • It is pointing to a good node

You can change the pointers of some nodes in order to make them all ‘good’.
You are given the description of the nodes.
You have to find out what is minimum number of nodes that you have to change in order
to make all the nodes good.

Input:
The first line of input contains an integer number N which is the number of nodes.
The next N lines contains N numbers,
all between 1 and N.
The first number, is the number of the node pointed to by Node 1;
the second number is the number of the node pointed to by Node 2;
the third number is the number of the node pointed to by Node 3 and so on.

N is no larger than 1000.

Output:
Print a single integer which is the answer to the problem

Sample Input 1:
5
1
2
3
4
5

Sample output 1:
4

Explanation:
We have to change pointers for four nodes (node #2 to node #5) to point to node #1.
Thus 4 changes are required

Sample input 2:
5
5
5
5
5
5

Sample output 2:
1

Link:Error: Question Does Not Exist | CareerCup

PS:Can u explain your approach?

2

#include <stdio.h>
int main() {
int n,i,ans=0;
scanf("%d",&n);
int a;
int c[1000]={0};
for(i=0;i<n;i++){
scanf("%d",&a);
c[a-1]=1;
}
for(i=1;i<;1000;i++){
if(c[i]==1)
ans++;
}
printf("%d",ans);
return 0;
}

I think this answer is perfect…

the input specifies that to which node current node points to…

now I ll count how may types of heads(except 1) are there…(like counting trees in a forest)

for example input is

   2 2 3 5 5 4 5

then I ll make one of
2 2 ,
one of
3
one of
4
and one from
5 5 5
to 1

as if i change one of them to point one then that node will become a “good node” and hence all other nodes connected to it will also become good nodes…
so for each different input count++
hence here set will be {2,3,4,5}
hence 4 is output…

3

see the comments of the question it has all the different approaches

4

though I cannot submit this soln for any corner cases… so pointing out if there is something wrong in this algo would be appreciated :slight_smile:

5

credits of soln to

Mohit Sati

6

he needs explanation bro :slight_smile: @ssp547
obviously he must and should have gone through comments once before posting…

1 Like
7

1 2 3

it wont work for this

8

Why ? Ans is 2 right ?

9

sorry…take 1 1 2…
yours will give answer as 1 but the correct answer is 0

10

Yup it’s a basic graph question. Find no. Of connected components using BFS or DFS is correct approach