d688: 无向图中子图的个数
Tags :
Accepted rate : 29人/37人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-04-05 22:38

Content
给你一张无向图,求出其连通子图的个数。
Input

每组测资第一行为n,m,(1<=n<=20,1<=m<=n*(n-1)/2)用一个空格隔开,分别表示该无向图的节点个数(其节点序号为1...N),该无向图的边数。

接下来有m行,x,y,用一个空格隔开,表示x和y是互相连通的。题目保证不会有重复的路径,而且节点没有连通自己的边。

读到 0 0 这组测资,结束程序。

Output
对于每组测资,输出它的子图的个数。
Sample Input #1
4 5
1 2
1 3
1 4
2 3
3 4
0 0
Sample Output #1
14
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :

BFS、DFS、DP....?反正AC就好。

如果您的程序在1s内通过本题,请将您的算法及程序代码写给本题的管理员进行参考,让他也学学好的算法。

测资有误请告诉管理员。

有问题可以问问...

 

范例测资的子图为:

{1} {2} {3} {4}
{1,2} {1,3} {1,4} {2,3} {3,4}
{1,2,3} {1,3,4} {1,2,4} {2,3,4}
{1,2,3,4}

一共14个。

 

对不起哟,有人说测试数据太弱,于是我只好加强一点。重测咯 2010/4/18 22:45pm

其实只有10笔测资,小心极限数据!

Tags:
出處:
morris1028 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」