/ Vijos / 题库 /

最大派系(与3248重复)

最大派系(与3248重复)

时间限制:1秒  内存限制:256M


【题目描述】

  给你一张有向图 G,求一个结点数最大的结点集,使得该结点集中的任意两个结点 u 和 v 满足:要么 u 可以达 v,要么 v 可以达 u(u,v相互可达也行)。

【输入格式】

  第一行为结点数 n 和边数 m ,结点编号 1~n。
  以下m行每行两个整数 u 和 v ,表示一条有向边 u->v。

【输出格式】

  输出最大结点集的结点数。

【输入输出样例1】

 Input

5 5
1 2
2 3
3 1
4 1
5 2

 Output

4

【测试点性质】

  对于全部的测试点,保证 \(2\le n \le 10^4\),\(2\le m\le 5\times 10^4\),\(1 \leq u, v \leq n\)。

【来源】

  Mr.he

信息

ID
3238
难度
9
分类
图结构 | 强连通分量拓扑排序动态规划 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
1
上传者