简单拓扑排序

拓扑排序 在有向图 中经常用来判断 是否存在 环.
若一个有向图中 存在 拓扑排序,则 一定不存在 环
若存在 环 ,则一定不存在 拓扑排序

举个例子 : 假设有 n 个变量,有 m 个二元组 (u,v),分别表示 变量u 小于 v.那么,所有变量从小到大排列起来.

例如:四个变量a,b,c,d,若已知 a < b,c < b ,d < c,则这 4 个变量的排序 可能是 a < d < c < b (答案不唯一,为什么?)

如图:
每次遍历 找到 当前入度为 0 的点,然后删除该点以及以该点为起点的边.

首先删掉结点 a ,及 a->b 的边

然后 删掉 d 及 d->c

删掉 c 及 c->b

删除结点的顺序 就为 拓扑排序后的顺序 (a -> d -> c -> b)

因为 开始时,a 和 d的 入度都为 0,所以答案不唯一 .
也可能是 d -> a -> c -> b

裸 拓扑排序

思路: 统计 各个结点的 入度 ,然后 维护一个 队列, 当 存在一个结点 的入度为 0, 将改点加入队.然后进入循环,若不存在 入度为0的点,则不存在拓扑排序.然后 以 队列 中元素为起点的边,将 其 终点的入度 减一 ,判断改点的入度是否为 0.若为0,加入队列.不为 0,则继续循环,当队列中没有元素时,退出循环. 记录进入队列元素的个数 cnt. 若 cnt == 总的点个数.则不存在环,进入队列的顺序就为拓扑排序的后的顺序.

核心代码

int toposort()
{
   
        while(!q.empty())  q.pop();
        for(int i = 0;i < n;i++)   if(!indeg[i]) q.push(i);

        while(!q.empty())
        {
   
                int temp = q.front();
                cnt++;
                q.pop();
    
                for(int i = 0;i < v[temp].size();i++)
                {
   
                        int x = v[temp][i];
                        indeg[x]--;
                        if(!indeg[x]) q.push(x);
                }
        }

        if(cnt == n)   return 1;
        else return 0;

}

(1)练习拓扑排序 --(板子题)

和(1)很类似稍微加了点需求

核心代码

virus[x] 表示第 x 个结点 的 病毒 数 (注意取余)

   virus[x] = (virus[x] + virus[temp])%mod;  

最后进行求和 最后注意取余

               sum += virus[i];
               sum = sum%mod;