Dominos 2(DFS)(容器)

http://acm.hdu.edu.cn/showproblem.php?pid=2754

大致意思：

有一堆骨牌，码好（当然不只是单线程，最初考虑单线程的，一直wa）

给你 n， m， l。n表示n张骨牌（从1-n标记），m表示 （x，y）对数，x倒了，y必倒，l 表示用手推倒的牌数，对应相应骨牌的标记号码。计算有几张骨牌倒了。

第一次开了10001*10001的数组来存，明显超内存了；

第二次用结构体来存（x，y）；

218MS 324K 793 B C++   46MS   540K   733 B   C++

   #include
   <
   stdio.h
   >
   
#include
   <
   algorithm
   >
   

   using
    
   namespace
    std;


   struct
    tree
{

   int
    x;

   int
    y;
}dimo[
   10001
   ];


   bool
    sign[
   10001
   ];

   int
    tot;

   int
    N,M,L;


   void
    DFS(
   int
    t)
{

   for
   (
   int
    i
   =
   1
   ; i
   <=
   M; i
   ++
   )

   if
   (dimo[i].x
   ==
   t)

   if
   (dimo[i].y 
   &&
    sign[dimo[i].y])
 { tot
   ++
   ;
 sign[dimo[i].y]
   =
   0
   ;
 DFS(dimo[i].y);
 }
}


   int
    main()
{ 

   /*
    freopen("input.txt", "r", stdin);
   */
   

   int
    case_,i,t;

   while
   (scanf(
   "
   %d
   "
   ,
   &
   case_)
   !=
   EOF)
 {

   while
   (case_
   --
   )
 {
 scanf(
   "
   %d%d%d
   "
   ,
   &
   N,
   &
   M,
   &
   L);

   for
   (i
   =
   1
   ; i
   <=
   N; i
   ++
   )
 sign[i]
   =
   1
   ;

   for
   (i
   =
   1
   ; i
   <=
   M; i
   ++
   )
 scanf(
   "
   %d%d
   "
   ,
   &
   dimo[i].x, 
   &
   dimo[i].y);

 tot
   =
   0
   ;

   for
   (i
   =
   1
   ; i
   <=
   L; i
   ++
   )
 {
 scanf(
   "
   %d
   "
   , 
   &
   t);

   if
   (sign[t])
 {
 tot
   ++
   ;
 sign[t]
   =
   0
   ;
 DFS(t);
 }
 }
 printf(
   "
   %d\n
   "
   , tot);
 }
 }

   return
    
   0
   ;
}
  

第三次用vector来存 x 后的所有 y；明显减少很多时间；

第一次用容器，容器不错；

46MS 540K 733 B C++

   #include
   <
   iostream
   >
   
#include
   <
   vector
   >
   

   using
    
   namespace
    std;

vector
   <
   int
   >
    dimo[
   10001
   ];

   bool
    sign[
   10001
   ];

   int
    tot;

   int
    N,M,L;


   void
    DFS(
   int
    t)
{

   if
   (
   !
   sign[t]) 
   return
    ;
 tot
   ++
   ;
 sign[t]
   =
   0
   ;

   int
    len
   =
   dimo[t].size();

   for
   (
   int
    i
   =
   0
   ; i
   <
   len; i
   ++
   )
 DFS(dimo[t][i]);
}


   int
    main()
{ 

   //
    freopen("input.txt", "r", stdin);
   

    
   int
    case_,i,t,x,y;

   while
   (scanf(
   "
   %d
   "
   ,
   &
   case_)
   !=
   EOF)
 {

   while
   (case_
   --
   )
 {
 scanf(
   "
   %d%d%d
   "
   ,
   &
   N,
   &
   M,
   &
   L);

   for
   (i
   =
   1
   ; i
   <=
   N; i
   ++
   )
 {
 dimo[i].clear();
 sign[i]
   =
   1
   ;
 }

   for
   (i
   =
   1
   ; i
   <=
   M; i
   ++
   )
 {
 scanf(
   "
   %d%d
   "
   ,
   &
   x, 
   &
   y);
 dimo[x].push_back(y);
 }
 tot
   =
   0
   ;

   for
   (i
   =
   1
   ; i
   <=
   L; i
   ++
   )
 {
 scanf(
   "
   %d
   "
   , 
   &
   t);
 DFS(t);
 }
 printf(
   "
   %d\n
   "
   , tot);
 }
 }

   return
    
   0
   ;
}