Country: United States

Comment hidden because of low score. Click to expand.
5
of 7 vote

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).

Comment hidden because of low score. Click to expand.
0

Step 2 is linear time, btw: we just run a depth-first search, which is linear because we have O(N) edges.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Why we should remove the edge from 1.
And How your solution work for sample test case 2.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

For sample2: there is only one connected component, but no pointer points to node 1, so we need to change one node in this case.
In summary:
1. Find connected components
2. Categorize connected components into three:
1). component that doesn't contain node1
2). component that contain node 1, but doesn't have a node point to it
3). component that contain node 1, but do have a node point to it
3. so the total number is:
1) + 2)

Comment hidden because of low score. Click to expand.
0

,

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

it seems correct, but i cant get why it's work.

Comment hidden because of low score. Click to expand.
0

this example doesnt work 2,3,4,2,6,5 expected 2, actual -1

Comment hidden because of low score. Click to expand.
0

glebstepanov1992, in my code I count from 0 to n-1 instead of from 1 to n. So the input for the example above should be {1,2,3,1,5,4} which yields the output 2 as desired.

Anyway, Julian offered a much more elegant solution below whose correctness is based on the following claims:

1. Let C be a (weakly) connected component in a directed graph. Suppose the incoming degree of each vertex in C is exactly 1. Then there exists some vertex r in C from for which every other vertex v in C is reachable from (in the directed graph). In other words, r is a root of C. This can be proved using the correctness of the algorithm for finding a root in a directed graph.

2. Let C be a (weakly) connected component in a directed graph. Suppose the incoming degree of every vertex in C, except some vertex r, is exactly 1 while r's incoming degree is 0. Then r is a root of C in the directed graph. This can be proved by simply determining the orientation of each edge in the undirected path from r to every other vertex in C (using the fact that the incoming degree is exactly 1 for every other vertex).

Removing the outgoing edge from the vertex 1 means that the vertex 1 has an incoming degree of 0 in the edge reversed graph while all the other vertices have an incoming degree of exactly 1. The claims above imply that by finding the number of (weakly) connected components in the new directed graph we'll be able to determine the minimum amount of roots in a dfs spanning forest where 1 is a root as well. So the answer would be the number of connected components minus 1 (for the component of the vertex 1) as Julian noted.

Comment hidden because of low score. Click to expand.
1
of 3 vote

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={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;
}

Comment hidden because of low score. Click to expand.
-2

This won't work when the input is 555555. It will state 4 changes when it should be 1.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;

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>();

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)){
}
}
}

Set<Node> rst = new HashSet<Node>();
for(int i = 1; i <= map.size(); i++){
if(!visited.contains(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++;

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

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

for(Node in : cur.ins){
if(nodes.contains(in) && !visited.contains(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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

}

//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];
}

i.remove();
changed = true;
}

}
} while (changed);

return communities.size() - 1;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

2 <- 3 <- 4 <- 5 has four SCCs

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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])

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It doesn't work after testing.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Count nodes except 1 that point to themselves

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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=1;
visited;

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;

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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=1;
visited;

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;

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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=1;
visited;

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;

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

(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.

Comment hidden because of low score. Click to expand.
0

This doesn't work because we don't need to modify every edge that initially has no path to node 1. It's possible to imagine a situation, for instance, where all nodes except node 1 form one giant cycle. If you now modify just any one node in the cycle to point to node 1, you will have a path for every node. The answer in that case would be 1 rather than N - 1.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

It's not necessary to be strongly connected, just connected.

Comment hidden because of low score. Click to expand.
1
of 1 vote

i think that we need strong connected components, because if we want to make set of nodes good, they must be interconnected. We have to choose such node , that will be connected to all other in set.

Comment hidden because of low score. Click to expand.
0

Consider the case where the graph looks like one big tree rooted at node 1, with an edge from each child to its parent. The answer is 0 because node 1 can be reached from all other nodes and there is therefore no need to change any of the edges. However, the entire tree is clearly not just one strongly connected component. You can see from this example that detecting SCCs doesn't give you the answer.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.util.HashSet;

public class GoodNodes {
public static void main(String [] argv) throws Exception {
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 = 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]) ){
}
} else { // equals
ret++;
}
}

}
return ret;
}

int [] ret = new int[n];
for(int i = 0; i < n ; i++){
}
return ret;
}

}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote
Actually, you do not need to maintain the goodTimes HashSet so the code after while can be: {{{ if(timestamps[c] == ts){ ret++; } }}
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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 ){
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];
}

}

Comment hidden because of low score. Click to expand.
0

try 1 2 3 4 3 and you'll find it does not work.

I guess we need to remove node 0 first.

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.