USACO 2009 Open Treasure Cave /// DFS||并查集 oj26215

题目大意:

输入 p，n，t ；p为地点数 判断 t 能否回到源点1

接下来n行 每行输入 a b c； a能到达b和c

Sample Input

13 6 7
6 7 8
2 3 4
10 11 12
8 9 10
1 2 13
4 5 6

Sample Output

5
1
2
4
6
7

 

可用深搜做

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int p,n,t;

int first[],nexti[],flag[];

int u[],v[],ans[],len;

bool DFS(int i,int cnt)

{

    if(i==t&&cnt<len)

    {

        len=cnt;

        ans[cnt]=i;

        return cnt;

    }

    if(cnt>len) return ;

    int k=first[i],sign=;

    while(k!=-)

    {

        if(!flag[v[k]])

        {

            flag[v[k]]=;

            if(DFS(v[k],cnt+)!=)

                ans[cnt]=i, sign=;

            flag[v[k]]=;

        }

        k=nexti[k];

    }

    if(sign) return cnt;

    else return ;

}

int main()

{

    while(~scanf("%d%d%d",&p,&n,&t))

    {

        memset(first,-,sizeof(first));

        memset(flag,,sizeof(flag));

        for(int i=;i<=n*;i++)

        {

            scanf("%d%d",&u[i],&v[i]);

            nexti[i]=first[u[i]];

            first[u[i]]=i++;

            u[i]=u[i-]; scanf("%d",&v[i]);

            nexti[i]=first[u[i]];

            first[u[i]]=i;

        }

        flag[]=;

        len=INF;

        DFS(,);

        printf("%d\n",len);

        for(int i=;i<=len;i++)

            printf("%d\n",ans[i]);

    }

    return ;

}

邻接表深搜

但用并查集更简单 还是简化的

#include<stdio.h>

int root[];

int get(int cnt,int m)

{

    if(m==)

    {

        printf("%d\n",cnt);

        return ;

    }

    if(get(cnt+,root[m]))

        printf("%d\n",root[m]);

}

int main()

{

    int p,n,t;

    while(~scanf("%d%d%d",&p,&n,&t))

    {

        for(int i=;i<=p;i++) root[i]=i;

        while(n--)

        {

            int a,b,c; scanf("%d%d%d",&a,&b,&c);

            root[b]=root[c]=a;

        }

        if(get(,t)) printf("%d\n",t);

    }

    return ;

}

并查集