ACM的一道题，我用DFS（深度优先遍历）结果被判定时间过长，是我写错了还是DFS不适合

cuibaowenown2

这是题目传送门：
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004
我的代码是：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max);
   
5. 
   
6. int main()
   
7. {
   
8.         int T;        //0<T<30
   
9.         int start,end;        //[0,100]
   
10.         int n;                //0<n<=50
    
11. 
    
12.         cin>>T;
    
13.         for (int i=0;i<T;i++)
    
14.         {
    
15.                 int max=-1;
    
16.                 bool station[150][150]={{false}};        //邻接矩阵
    
17.                 bool column[150]={false};                //记录某列是否已经走过
    
18.                 cin>>start>>end>>n;
    
19.                 int temp,before;
    
20.                 while (1)
    
21.                 {
    
22.                         if ('\n' == cin.peek())
    
23.                         {
    
24.                                 before=-1;
    
25.                                 if (0 == n--)        break;
    
26.                         }
    
27.                         cin>>temp;
    
28.                         if (temp > max)        max=temp;
    
29.                         if (-1 == before)        before=temp;
    
30.                         else if (temp == before)        continue;
    
31.                         else        station[temp][before]=station[before][temp]=true;
    
32.                 }
    
33.                 if (DFS(station,start,0,end,column,max))        cout<<"Yes"<<endl;
    
34.                 else        cout<<"No"<<endl;
    
35.         }
    
36.         return 0;
    
37. }
    
38. 
    
39. bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max)
    
40. {
    
41.         if (posy == end && true == station[posx][end])
    
42.                 return true;
    
43.         else if (posy > max)
    
44.                 return false;
    
45. 
    
46.         if (true == station[posx][posy] && false == column[posy])
    
47.         {
    
48.                 column[posy]=true;
    
49.                 if (DFS(station,posy,0,end,column,max))        return true;
    
50.                 column[posy]=false;
    
51.         }
    
52.         return DFS(station,posx,posy+1,end,column,max);
    
53. }

复制代码

系统说我执行时间超过了1s，是不是DFS在此不适用？:mad:

rockerz

这道题只给你1s的时间但给了你128mb的内存，明显是要你用内存来换时间。用并查表会快很多。union find disjoint set。
http://zh.wikipedia.org/zh-sg/%E5%B9%B6%E6%9F%A5%E9%9B%86

1. #include <cstdio>
   
2. #include <iostream>
   
3. using namespace std;
   
4. int rank[1000000];
   
5. int p[1000000];
   
6. 
   
7. void makeset(int x){
   
8.         p[x]=x;
   
9.         rank[x]=0;
   
10. }
    
11. 
    
12. int findp(int x){
    
13.           if (p[x] != x)p[x]=findp(p[x]);
    
14.           
    
15.           return p[x];
    
16. }
    
17. 
    
18. void unionset(int x, int y){
    
19.         int xp,yp;
    
20.         xp=findp(x);
    
21.         yp=findp(y);
    
22.         if (xp==yp)return;
    
23.        
    
24.         if (rank[xp]<rank[yp])p[xp]=yp;
    
25.         else if (rank[xp]>rank[yp])p[yp]=xp;
    
26.         else  { //if equal
    
27.                 p[yp]=xp;     
    
28.                 rank[xp]++;
    
29.         }
    
30. }
    
31. 
    
32. 
    
33. int main()
    
34. {
    
35.         bool firstc=true;
    
36.         int t,n,x,s,e,i=0;
    
37.         int temp;
    
38.         scanf ("%d",&t);
    
39.         while (t--){
    
40.                 scanf("%d%d",&s,&e);
    
41.                 scanf("%d",&n);
    
42.                 while (n--){
    
43.                         if (firstc)scanf("%d",&temp); //skip first c
    
44.                         int x1;
    
45.                         while (1){
    
46.                                 if (cin.peek()=='\n')break;
    
47.                                 if (i!=0)x1=x;
    
48.                                 scanf("%d",&x);
    
49.                                 makeset(x);
    
50.                                 if (i!=0){
    
51.                                         unionset(x,x1);
    
52.                                 }
    
53.                                 i++;
    
54.                         }
    
55.                         firstc=true;
    
56.                 }
    
57.                 if (findp(s)==findp(e))printf("Yes\n");
    
58.                 else printf("No\n");
    
59.                
    
60.         }
    
61.        
    
62.        
    
63.         return 0;
    
64. }
    

复制代码

你可以拿去试试，反正他给的Test case都过关了。还有就是你应该学会用cstdio中的scanf()和printf()。这两个比Cin和cout要快很多，有的时候他给的数据庞大了，时间差距就十分明显了。

cuibaowenown2

rockerz 发表于 2014-4-18 10:54

                               
登录/注册后可看大图

这道题只给你1s的时间但给了你128mb的内存，明显是要你用内存来换时间。用并查表会快很多。union find disj ...

你的也是Time Limit:titter:

rockerz

这。。。我也不清楚了。。学艺不精啊。。