问题陈述
给出N个节点的有向图,其中每个节点都指向N个节点中的任何一个(可能指向自身)。编码员Ishu很无聊,他发现了一个问题,以使自己保持忙碌。问题如下:
如果节点满足以下条件之一,则它是“好”:
- 这是特殊节点(标记为节点1)
- 它指向特殊节点(节点1)
- 它指向一个好的节点。 Ishu将更改某些节点的指针,以使其全部“良好”。您必须找到要更改的最小指针数,以使所有节点均良好(因此,是良好的图形)。
注意:结果图应具有所有节点均良好且每个节点必须精确指向一个节点的属性。
问题约束
1
输入格式
第一个也是唯一的参数是一个整数数组A,它包含N个在1到N之间的数字,其中第i个数字是第i个节点指向的节点数。
输出格式
一个整数,表示最小的指针更改数。
我尝试过的解决方案
我尝试通过反转边缘来构建图形,然后尝试为连接的节点着色,答案将是colors - 1
。简而言之,我试图为一个有向图找到连接的组件的数量,这是没有意义的(因为有向图没有任何有关连接组件的概念)。网络上的其他解决方案,例如this和this也指出要查找连接的组件的数量,但是对于一个有向图来说,连接的组件再次对我来说没有任何意义。对我来说,这个问题比它的初看起来要棘手得多。