题目:
农夫约翰的奶牛通常是按1到N进行编号的,奶牛们相互之间有一种特殊的信息传输方式。在信息传递的过程中,每只奶牛的信息最多传递到另一只奶牛,对于奶牛i,Fi表示他要传递信息的那只奶牛的编号,这里i和Fi肯定是不同的,如果Fi是0,则表示奶牛i没有要传递信息给其他的奶牛。
不幸的是,奶牛们知道了这种传递信息的方式可能会导致一个死循环。如果一个奶牛传递信息最终会导致一个死循环,那么我们就说这只奶牛在死循环里面。
问题描述:
农夫约翰的奶牛通常是按1到N进行编号的,奶牛们相互之间有一种特殊的信息传输方式。在信息传递的过程中,每只奶牛的信息最多传递到另一只奶牛,对于奶牛i,Fi表示他要传递信息的那只奶牛的编号,这里i和Fi肯定是不同的,如果Fi是0,则表示奶牛i没有要传递信息给其他的奶牛。
不幸的是,奶牛们知道了这种传递信息的方式可能会导致一个死循环。如果一个奶牛传递信息最终会导致一个死循环,那么我们就说这只奶牛在死循环里面。
问题描述:
请帮助奶牛们计算有多少头奶牛没有在死循环里面。
题解:
最后不指向0的牛都死了。
代码:
vara,b:array[1..10000] of longint;f:array[0..10000] of boolean;n,i,j,l:longint;
beginassign(input,'relay.in');reset(input);assign(output,'relay.out');rewrite(output);readln(n);for i:=1 to n doreadln(a[i]);fillchar(b,sizeof(b),0);for i:=1 to n dobeginj:=i;fillchar(f,sizeof(f),false);while j>0 dobeginif f[j] thenbeginf[0]:=true;break;end;f[j]:=true;j:=a[j];end;if f[0] thenfor j:=1 to n doif f[j] then b[j]:=1;end;for i:=1 to n doif b[i]=0 then inc(l);writeln(l);close(input);close(output);
end.