问题 C: 网络

问题 C: 网络

时间限制: 1 Sec  内存限制: 128 MB
提交: 36  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

在计算机科学中,经常要通过分析变量之间的相关性来简化计算过程。变量 间的相关性可以用有向图G=(V,E)来表示,图中的点表示变量,边表示变量间 的关系。这里G满足:G中的所有边都从编号小的点指向编号大的点。 从图中选出一个点集T⊆V,如果T中的任意两个点之间都有边(方向是编 号小的点指向编号大的点),则称T为团。特别地,空集也认为是一个团。 如果存在一个点,与T中的任意一个点之间都有边(方向是编号小的点指 向编号大的点),那么称T为可扩团。 如果一个团S不是可扩团,那么称它为极大团。 给出G,求G有多少个不同的极大团。 这里G满足一个性质:对于G中任意一个点i,用H[i]表示编号比i小的点 中所有与i有边相连的点的集合,那么H[i]是一个团。 

输入

第一行n,m,表示点数和边数 接下来m行,每行两个数a,b,表示有从a到b的边 注意可能有重边 保证输入的图满足问题描述中提到的性质。 

输出

极大团数量

样例输入

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

样例输出

2

提示

对于30%的数据, n<=10
对于60%的数据, n<=1000
对于100%的数据, n,m<=1000000

[提交][状态]