xie_lzh @ 2022-01-17 16:56:33
在本题的第二篇题解中有着这样一段代码
for(int x=1;x<=n;x++) {
f[x]=size[x];
g[x]=1;
for(int i=Head[x];i;i=Next[i]) {
int y=ver[i];
if(belong[x]==belong[y]) continue;
ADD(belong[x],belong[y]);
}
}在其中第二行的对 f数组 的初始化中 按照我的理解应该是对 缩点 后每一个点进行初始化 而不是对 1到 n 的每一个点初始化
我有点不明白 希望有daolao能回答
by CloudyKai @ 2022-02-09 23:37:22
首先我的理解也是这样
然后缩之后的点编号是1到scc，其中scc小于n，所以这么一次就可以把1到scc的新点都初始化f和g，至于剩下的部分程序也不会再用了，不用去管
for循环从1到n主要是为了下面的，把缩点前的图转化为缩点后的图，要枚举缩点前的n个点
所以要规范逻辑的话，前3行和后6行应该分两个for循环写的，只不过为了详略得当合并了一下
隔了二十几天，大佬想必早就想明白了吧(我在写啥
（话说我还没A这道题，来教大佬看题解干嘛）