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

cuibaowenown2

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

#include <iostream>
using namespace std;

bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max);

int main()
{
        int T;        //0<T<30
        int start,end;        //[0,100]
        int n;                //0<n<=50

        cin>>T;
        for (int i=0;i<T;i++)
        {
                int max=-1;
                bool station[150][150]={{false}};        //邻接矩阵
                bool column[150]={false};                //记录某列是否已经走过
                cin>>start>>end>>n;
                int temp,before;
                while (1)
                {
                        if ('\n' == cin.peek())
                        {
                                before=-1;
                                if (0 == n--)        break;
                        }
                        cin>>temp;
                        if (temp > max)        max=temp;
                        if (-1 == before)        before=temp;
                        else if (temp == before)        continue;
                        else        station[temp][before]=station[before][temp]=true;
                }
                if (DFS(station,start,0,end,column,max))        cout<<"Yes"<<endl;
                else        cout<<"No"<<endl;
        }
        return 0;
}

bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max)
{
        if (posy == end && true == station[posx][end])
                return true;
        else if (posy > max)
                return false;

        if (true == station[posx][posy] && false == column[posy])
        {
                column[posy]=true;
                if (DFS(station,posy,0,end,column,max))        return true;
                column[posy]=false;
        }
        return DFS(station,posx,posy+1,end,column,max);
}

系统说我执行时间超过了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

#include <cstdio>
#include <iostream>
using namespace std;
int rank[1000000];
int p[1000000];

void makeset(int x){
        p[x]=x;
        rank[x]=0;
}

int findp(int x){
          if (p[x] != x)p[x]=findp(p[x]);
          
          return p[x];
}

void unionset(int x, int y){
        int xp,yp;
        xp=findp(x);
        yp=findp(y);
        if (xp==yp)return;
        
        if (rank[xp]<rank[yp])p[xp]=yp;
        else if (rank[xp]>rank[yp])p[yp]=xp;
        else  { //if equal
                p[yp]=xp;     
                rank[xp]++;
        }
}


int main()
{
        bool firstc=true;
        int t,n,x,s,e,i=0;
        int temp;
        scanf ("%d",&t);
        while (t--){
                scanf("%d%d",&s,&e);
                scanf("%d",&n);
                while (n--){
                        if (firstc)scanf("%d",&temp); //skip first c
                        int x1;
                        while (1){
                                if (cin.peek()=='\n')break;
                                if (i!=0)x1=x;
                                scanf("%d",&x);
                                makeset(x);
                                if (i!=0){
                                        unionset(x,x1);
                                }
                                i++;
                        }
                        firstc=true;
                }
                if (findp(s)==findp(e))printf("Yes\n");
                else printf("No\n");
                
        }
        
        
        return 0;
}

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

cuibaowenown2

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

                               
登录/注册后可看大图

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

你的也是Time Limit:titter:

rockerz

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