CareerCup

1. Remove the edge (pointer) from 1.
2. Find connected components.
3. The answer is the number of connected components - 1 (i.e. all the connected components except for the one that contains 1).

I think this problem can be reduced to finding a spanning dfs forest with minimum number of trees.

1. First, we'll create a new graph by reversing all the edges in original input graph, this graph will simply be denoted by G. Notice that all the vertices reachable from 1 in G are "good vertices".

2. We'll build a stack of the roots of the dfs forest which is the result of running dfs on G starting from the vertex 1 and when you need to select a new root, select the minimum possible (notice that if all the vertices are reachable from 1 then instead of a forest we have a single tree). Whenever we encounter a new root throughout the dfs run we'll just push it to the stack.

3. We'll run dfs again on G but this time, instead of starting from 1, we'll use the roots stack from (2) whenever we need a new root to traverse from (roots that were already encountered throughout the dfs run will just be popped and ignored). Throughout this dfs run we'll yet again build a root stack of the roots in the dfs forest (for this dfs run).

4. The resulting root stack from step (3) should contain the minimum number of trees in the dfs forest for the graph G (considering the special structure of G - exactly 1 incoming edge to each vertex). The result is the number of roots in the stack from (3) minus 1 if 1 is a root as well.

Complexity: Two dfs runs - O(n) (the number of vertices and edges is O(n)).

Code: snipt.org/BihG4

It is so simple why people are even using any algorithms

#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;
}

1. build graphs: label -> Node
2. remove all nodes point to(directly or in-directly) #1
3. count remaining independent graphs

import java.util.*;

class GoodNodes{
  public static void main(String[] args){
    //int[] array = {1,2,3,4,5};
    int[] array = {5,5,5,5,5};

    GoodNodes s = new GoodNodes();
    int rst = s.needChange(array);

    Helper.p(rst);
  }

  int needChange(int[] array){
    //1. build graphs: label -> Node
    Map<Integer, Node> map = buildMap(array);

    //remove all nodes point to(directly or in-directly) #1
    Set<Node> remaining = removeGoodNodes(map);

    //count remaining independent graphs
    int rst = countNumOfGraphs(remaining);

    return rst;
  }

  Map<Integer, Node> buildMap(int[] array){
    Map<Integer, Node> map = new HashMap<Integer, Node>();

    for(int i = 0; i < array.length; i++){
      int cur = i + 1;
      int to = array[i];

      if(cur == to){
        Node node = map.containsKey(cur)? map.get(cur):new Node(cur);
        map.put(cur, node);
      }else{
        Node curNode = map.containsKey(cur)? map.get(cur):new Node(cur);
        Node toNode = map.containsKey(to)? map.get(to): new Node(to);

        curNode.out = toNode;
        toNode.ins.add(curNode);

        map.put(cur, curNode);
        map.put(to, toNode);
      }
    }

    return map;
  }

  Set<Node> removeGoodNodes(Map<Integer, Node> map){
    Node origin = map.get(1);

    Set<Integer> visited = new HashSet<Integer>();
    LinkedList<Integer> q = new LinkedList<Integer>();
    visited.add(1);
    q.add(1);

    while(!q.isEmpty()){
      int cur = q.remove();

      Node node = map.get(cur);
      for(Node n: node.ins){
        int label = n.label;

        if(!visited.contains(label)){
          visited.add(label);
          q.add(label);
        }
      }
    }

    Set<Node> rst = new HashSet<Node>();
    for(int i = 1; i <= map.size(); i++){
      if(!visited.contains(i)){
        rst.add(map.get(i));
      }
    }

    return rst;
  }

  //count piece of parts
  int countNumOfGraphs(Set<Node> nodes){
    int rst = 0;
    //bfs
    Set<Node> visited = new HashSet<Node>();

    for(Node node: nodes){
      if(!visited.contains(node)){
        rst++;

        LinkedList<Node> q = new LinkedList<Node>();
        visited.add(node);
        q.add(node);

        while(!q.isEmpty()){
          Node cur = q.remove();

          Node out = cur.out;
          if(out != null && nodes.contains(out) && !visited.contains(out)){
            visited.add(out);
            q.add(out);
          }

          for(Node in : cur.ins){
            if(nodes.contains(in) && !visited.contains(in)){
              visited.add(in);
              q.add(in);
            }
          }
        }
      }
    }

    return rst;
  }

  class Node{
    int label;

    Node out;
    List<Node> ins;

    public Node(int label){
      this.label = label;
      this.ins = new ArrayList<Node>();
    }
  }
}

//TEST
//1,2,3,4,5 => 4
//5,5,5,5,5 => 1

public class GoodBadNodes {
    public static void main(String... args) {
        System.out.println(goodNodes(new int[]{5, 3, 1, 5, 2}));
    }

    static int goodNodes(int[] points_to) {
        //there is one "good" community and some "bad" comunities
        //the answer to the problen is the number of isolated bad communities.
        //or at least i suppose so...

        Map<Integer, Set<Integer>> communities = new HashMap<>();
        communities.put(1, new HashSet<>());

        for (int i = 1; i < points_to.length; i++) {
            Set<Integer> community = communities.get(points_to[i]);
            if (community == null) {
                community = new HashSet<>();
                communities.put(points_to[i], community);
            }

            community.add(i);
        }

        //make communities larger until they don't change
        boolean changed;
        do {
            changed = false;
            for (Iterator<Integer> i = communities.keySet().iterator(); i.hasNext(); ) {
                int index = i.next();
                if (index == 1) {
                    continue;
                }
                Set<Integer> community = communities.get(index);
                //if points to itself - continue
                if (points_to[index - 1] == index) {
                    continue;
                }

                Set<Integer> newCommunity = communities.get(points_to[index - 1]);
                if (newCommunity != null) {
                    //make old community members to point to the new community
                    for (Integer member : community) {
                        points_to[member] = points_to[index - 1];
                    }

                    newCommunity.addAll(community);
                    i.remove();
                    changed = true;
                }

            }
        } while (changed);

        return communities.size() - 1;
    }
}

}

1. Find all good nodes from the begging.( BFS or DFS)
2. Then Find all strong connected components. From those node, who arent good.
Answer uis a number of SCC.

keep a map M of lists such that map.get(i) = lists of nodes that points to (i) minus the i-th node;
also keep a set S of good nodes, initialize with the tail node;
then starting from the list of nodes that point to the tail node, proceed the lists and mark every node a good node (put it in the set S); repeat this step with nodes in the list;
finish when every node in the list is already a good node or the list is empty;

public static int nChangesToMakeAllNodesGood(List<Integer> nodes_list)
    {
        if(nodes_list.isEmpty())
            return 0;

        // list of marked items
        List<Integer> visited_list = new ArrayList<Integer>(nodes_list.size());
        for(int i = 0; i < visited_list.size(); ++i)
            visited_list.set(i, -1);
        
        int ncomponents = 1, npass = 0;
        visited_list.set(0, 0);
        for(int i = 0; i < nodes_list.size(); ++i)
        {
            if( isNewComponent(nodes_list, visited_list, i, npass++) )
                ++ncomponents;
        }
        
        return ncomponents-1;        
    }
    public static Boolean isNewComponent(List<Integer> nodes_list, List<Integer> visited_list, int i, int cur_pass)
    {
        // delete link from first node: if first node, then it's an old component and return
        if(i == 0)
            return false;

        // found node visited on previous passes: old component
        if(visited_list.get(i) > 0 && visited_list.get(i) != cur_pass )
            return false;
        // found node visited in this pass: new component
        if(visited_list.get(i) == cur_pass)
            return true;
        // current node hasn't been visited: mark as cur_pass
        visited_list.set(i, cur_pass);
        
        return isNewComponent(nodes_list, visited_list, nodes_list.get(i), cur_pass);  
    }

I think this one works. I haven't studied much Graph theory but this was what came to my mind.

def find_root(arr, i):
	if(arr[i] == i):
		return i
	return find_root(arr, arr[i])

def count_max_nodes(arr):
	for i in range(len(arr)):
		arr[i] = arr[i] - 1
	temp = {}
	for i in range(1,len(arr)):
		root = find_root(arr,i)
		if root != 0:
			temp[root] = 1
	
	print(len(temp))

count_max_nodes([1,2,3,4,5])
count_max_nodes([5,5,5,5,5])
count_max_nodes([1,5,1,2,5])

1) assign each node with its idx, parent, rank(initially will be '0')
example. for input 1, 2, 3, 3, 5 , it will be {[1, 1, 0], [2, 2, 0], [3, 3, 0], [4, 3, 0], [5, 5, 0]}
2) go through the list and assign rank by finding parent of each node
for the above input, it will be {[1, 1, 1], [2, 2, 1], [3, 3, 2], [4, 3, 0], [5, 5, 0]}
3) Now go through the list and count non zero rank nodes except first node(its already tail node).
for the above input, it will be 2, 3, 5 with non zero ranks, so the count is 3.. you need to change nodes to make all nodes to be good node.

Why aren't we just counting the nodes that are pointing to themselves? Just exclude the first node

Count nodes except 1 that point to themselves

Isn't this a normal BFS with maintaining the visted nodes.
Count the number of nodes we get while traversing and subtract that from the total count?

Based on @Julian's idea, the solution can be based on union-find method. union all connected nodes. count total groups number M. if there's a group which the good node is the root, than return M-1, else return M.
An optimised union-find algorithms takes almost o(n) to union all nodes. So the time and space complexity of this algorithms is o(n)

class Solution{
    int[] list=null;
    int count=0;
    public int getMinNodesToChange(int[] nodes){
        int N=nodes.length;
        count=N;
        list=new int[N+1];
        for (int i=1; i<=N; i++) list[i]=i;
        int flag=0;
        for (int i=1; i<=N; i++){
            if (nodes[i-1]==1) flag=1;
            union (i, nodes[i-1]);
        }
        return count - flag;
    }  
    public void union(int i, int j){
        int rootI=findRoot(i);
        int rootJ=findRoot(j);
        if (rootI==rootJ) return;
        list[rootJ]=rootI;
        count--;
    }
    public int findRoot(int i){
        while (list[i]!=i){
            int tmp=list[i];
            list[i]=list[tmp];
            i=tmp;            
        }
        return i;
    }
}

if there is no cycle then we just need to find the node pointing itself
Code in Python

n=6
l=[5,5,5,5,5]
change = []
for i in range(1,len(l)):
	j=i+1
	if(l[i]==j):
		change.append(l[i])
length = len(change)
print(length)

that was just max 15-20 line code .. dont know y u guys writing large program

#include<iostream>
using namespace std;

int fun(int arr[],int k,int []);

int main()
{
int n;
cin>>n;
int arr[n+1]={0},ar[n+1]={0};
for(int i=1;i<=n;i++)
cin>>arr[i];
arr[1]=-1;

int sum=0;
for(int i=2;i<=n;i++)
if(fun(arr,i,ar)==-1)
sum+=1;
cout<<sum;



return 0;
}

int fun(int arr[],int k,int ar[])
{
if(arr[k]==-1 || arr[k]==-2) return -2;

if(ar[k]>0) return -1;
ar[k]+=1;

arr[k]=fun(arr,arr[k],ar);

return arr[k];
}

#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define pb push_back
vector<int> v[1000];
int r[1000]={0};
int vis[1000]={0};
int dfs(int x)
{

   // cout<<"x "<<x<<endl;
    vis[x]=1;

        if(!vis[v[x][0]])
        {
            //cout<<"here\n";
            int z=dfs(v[x][0]);
            if(z==-1)
                return x;
            else
            {
                r[x]=z;
                return z;
            }
        }
        else
        {
            //r[x]=r[i];
            //cout<<"returning "<<x<<" = "<<r[v[x][0]]<<endl;
            r[x]=r[v[x][0]];
            return r[v[x][0]];
        }
    return -1;
}

int main()
{

    int n;
    cin>>n;
    int i;
    //v.resize(n+1);

    for(i=1;i<=n;i++)
        r[i]=i;
    for(i=1;i<=n;i++)
    {
        int x;
        cin>>x;

        v[i].pb(x);
    }
    for(i=1;i<=n;i++)
    {

        if(!vis[i])
        {
           // cout<<"For i "<<i<<endl;
            dfs(i);
        }
    }
    /*
    for(i=1;i<=n;i++)
        cout<<r[i]<<" ";
    cout<<endl;*/
    int ch=1;
    map<int,int> m;
    for(i=2;i<=n;i++)
    {
        if(r[i]!=ch)
        {
            m[r[i]]++;
        }
    }
    cout<<m.size()<<endl;
}

int good_graph(vector<int> nodes)
{
	int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
    		
    		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;

}

int good_graph(vector<int> nodes)
{
	int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
    		
    		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;
	
}

int good_graph(vector<int> nodes)
{int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
   		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;

}

We can use Union find data structure and it making everything simple right ??

(1) Scan the list, for each node U if U points to V and V is not U, mark node U (there's an out going edge from U)

(2) Scan the list and count the number of node V that is not marked in (1) and that is not the tail.

Create a graph. First run strong connected component algorithm, in the SCCG count nodes without outgoing edges.

Most answers here over-complicate the problem to graph algorithms. An O(n) time solution with O(n) space complexity is given below. The solution associates timestamps with (threads of) nodes and uses these timestamps to determine whether the encountered node is undiscovered, good or bad. No actual nodes are created all the data is maintained in two arrays of size n.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class GoodNodes {
	 public static void main(String [] argv) throws Exception {
		 int [] nodes = readNodes(new BufferedReader(new InputStreamReader(System.in)));
		 int changeCnt = getNumRedirects(nodes);
		 System.out.println("Result is " + changeCnt);



	 }

	 public static int getNumRedirects(int [] nodes){
		 int n = nodes.length;
		 if(n < 1) return 0;
		 int [] timestamps = new int[n];
		 int ts = 1;
		 HashSet<Integer> goodTimes = new HashSet<>();
		 timestamps[0] = ts;
		 int ret = 0 ;
		 for(int i = 1; i < n ; i++){
			 if(timestamps[i] <= 0) {
				 ts++;
				 int c = i;
				 while(timestamps[c] <=0){
					 timestamps[c] = ts;
					 c = nodes[c];
				 }
				 if(timestamps[c] < ts){
					 if(goodTimes.contains(timestamps[c]) ){
						 goodTimes.add(ts);
					 }
				 } else { // equals
					 ret++;
				 }
			 }		

		 }
		 return ret;
	 }


	 private static int [] readNodes(BufferedReader ps) throws Exception {
		 int n = readInt(ps);
		 int [] ret = new int[n];
		 for(int i = 0; i < n ; i++){
			 ret[i] = readInt(ps)-1;
		 }
		 return ret;
	 }

	 private static int readInt(BufferedReader ps) throws Exception {
		 return Integer.parseInt(ps.readLine().trim());
	 }


 }

1. We just need to detect cycles and trees, later we need just count them as in cycle we can change any node to point to first node and in tree we need to change only root node to pointing to first node, the alg quite similar to union find

public static void main(String[] args) {
        int[] nodes = {0,2,3,4,0};
        //int[] nodes = {5, 2, 3, 4, 1, 0, 0};
        int[] clusters = new int[nodes.length];
        for (int i = 0; i < clusters.length; i++) {
            clusters[i] = -1;
        }

        for (int i = 0; i < clusters.length; i++) {
            if (clusters[i] == -1) {
                int s = mark(i, i, clusters, nodes);

                if (s != i) {
                    for (int j = 0; j < clusters.length; j++) {
                        if (clusters[j] == i) {
                            clusters[j] = s;
                        }
                    }
                }
            }
        }

        //System.out.println(Arrays.toString(clusters));

        int[] count = new int[nodes.length];
        int sum = 0;
        for (int cluster : clusters) {
            if (count[cluster] == 0) {
                count[cluster] = 1;
                sum++;
            }
        }

        //System.out.println(Arrays.toString(count));

        if( clusters[0] == 0 ){
            sum--;
        }

        System.out.println(sum);
    }

    public static int mark(int cluster, int i, int[] clusters, int[] nodes) {
        if (clusters[i] == -1) {
            clusters[i] = cluster;
            if (nodes[i] != i) {
                return mark(cluster, nodes[i], clusters, nodes);
            } else {
                return i;
            }
        } else {
            return clusters[i];
        }

}

For this input we just have to keep a set of unique numbers different then 1.
These are nodes which are connected neither to tail nor any 'good' node.
The size of the set is the number of nodes which have to be changed.
For the examples given in question:
a) 5 5 5 5 5 5 - set is {5} - change one element the remaining elements are pointing to it.
b)1 2 3 4 5 - set is {2 3 4 5} - None of the nodes is connected to the 'good' node so all of them have to be changed.
I don't see any reason to construct a graph while we are able to determine the connections based on the node's values.