有向图中的强连通分量在Kosaraju算法中具有重要性
发布时间
阅读量:
阅读量
受欢迎的牛
每头牛都渴望成为最受其他牛欢迎的存在。
现有 N 头牛,编号为 1 至 N,给出 M 对整数 (A,B),表示牛 A 视牛 B 为受欢迎的对象。
这种关系具有传递性质,若 A 认为 B 受欢迎,而 B 认为 C 受欢迎,则 A 同样会认为 C 受欢迎。
你的任务是确定有多少头牛被除自身以外的所有其他牛视为受欢迎的对象。
输入格式
第一行包含两个整数 N 和 M;
接下来的 M 行中,每行给出两个整数 A 和 B,表示 A 将 B 视为受欢迎的个体(输入数据可能存在重复的情况)。
输出格式
输出被除自己之外的所有牛都认为受欢迎的牛的数量。
数据范围
1≤N≤10^4,
1≤M≤5×10^4
输入样例:
3 3
1 2
2 1
2 3
输出样例:
1
样例解释
仅有第三头牛被除自己以外的所有其他牛认为是受欢迎的。
题解:
首先对这道题目进行分析,若存在两个节点的出度为0,则结果直接为0。否则,我们进一步探讨,完成奶牛缩点操作后,所形成的图结构必然是一个有向无环图(DAG)。此时,位于出度为0的强连通分量中的奶牛数量即为最终的答案。
#include <bits/stdc++.h>
using namespace std;
const int
全部评论 (0)
还没有任何评论哟~
