/* 天衣无缝 */
by Wou_Red @ 2018-10-24 15:25:54
%%%%
by Ink_Cat @ 2018-10-24 15:26:05
%%%
by 猫脑 @ 2018-10-24 15:26:12
拓扑出错了,原题要求的是选定点出发,而在拓扑过程中逐渐减掉某些点父亲数量,只有当父亲数为0时,才入队。仔细看,这是一般的从入度为0的节点开始的拓扑,每个点最后都会入队,但我们选定的c出发点会导致一些点的父节点无法从出发点开始去访问,自然无法减去他们对子节点的影响。因此,可以添加以下简短的维护父亲数量的代码。
```cpp
void dfs(int x)
{
ex[x]=1;
for(int i=0;i<mp[x].size();i++){
node y=mp[x][i];
if(!ex[y.to])dfs(y.to);
}
}
void del()
{
queue<int>qy;
for(int i=1;i<=tmp;i++){
if(!fa[i]&&!ex[i])qy.push(i);
}
while(!qy.empty())
{
int x=qy.front();qy.pop();
for(int i=0;i<mp[x].size();i++){
node y=mp[x][i];
fa[y.to]--;
if(!ex[y.to])qy.push(y.to);
}
}
}
```
ex数组代表出发点可以访问到的点,先通过搜索预处理掉可以到的点,再del掉访问不到的点对子节点的影响。然后就可以正常通过了。
by TheOnlyMan @ 2021-04-16 12:26:47