问题 4355 --网络

4355: 网络

时间限制: 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

来源

提高组模拟测试3 

[提交][状态]