Posted on 2009-06-03 12:34
Hero 閱讀(134)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1227 Accepted 0 176 948 C++
2
3 //深度優先搜索
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 15 ;
10 int edge[size][size] ;
11
12 int tnum ;
13 int inn, inm, inx ;
14 int out ;
15
16 int visited[size] ;
17
18 void DFS( int sn, int cnt )
19 {
20 if( cnt == inn && 0 == sn ) out = out + 1 ;
21
22 visited[sn] = 1 ;
23 for( int i=0; i<=inn; i++ )
24 {
25 if( 0 == visited[i] && 1 == edge[sn][i] ) DFS( i, cnt+1 ) ;
26 }
27 visited[sn] = 0 ;
28 }
29
30 int main()
31 {
32 while( scanf( "%d", &tnum ) != EOF )
33 {
34 while( tnum -- )
35 {
36 scanf( "%d", &inn ) ;
37 memset( edge, 0, sizeof(edge) ) ;
38 memset( visited, 0, sizeof(visited) ) ;
39
40 for( int i=1; i<=inn; i++ )
41 {
42 scanf( "%d", &inm ) ;
43 for( int j=1; j<=inm; j++ )
44 {
45 scanf( "%d", &inx ) ;
46 edge[i][inx] = edge[inx][i] = 1 ;
47 }
48 }//input
49
50 out = 0 ;
51 for( int i=1; i<=inn; i++ )
52 {
53 if( 1 == edge[0][i] ) DFS( i, 0 ) ;
54 }
55
56 printf( "%d\n", out ) ;
57 }
58 }
59 return 0 ;
60 }