图的深度遍历

ゞ浴缸里的玫瑰 2022-07-12 06:50 151阅读 0赞

#### Problem Description ####

请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。

#### Input ####

输入第一行为整数n（0 < n < 100），表示数据的组数。 对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k\*k），表示有m条边，k个顶点。 下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

#### Output ####

输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。

#### Example Input ####

1
    4 4
    0 1
    0 2
    0 3
    2 3

#### Example Output ####

0 1 2 3

#include<stdio.h>
    #define max 100
    int df[max][max];
    int book[max];
    int num[max];
    int top;
    void dfs(int x)
    {
        int i;
        num[++top]=x;
        book[x]=1;
        for(i=1;i<max;i++)
        {
            if(df[x][i]!=0&&book[i]==0)
            {
                dfs(i);
            }
        }
        return ;
    }
    int main()
    {
        int i,t,n,k,m,u,v,min;
        scanf("%d",&t);
        while(t--)
        {
            memset(book,0,sizeof(book));
            memset(df,0,sizeof(df));
            min=0x3f3f3f3f;
            top=-1;
            scanf("%d%d",&k,&m);
            while(m--)
            {
                scanf("%d%d",&u,&v);
                df[u][v]=df[v][u]=1;
                if(u<min)
                    min=u;
            }
            dfs(min);
            for(i=0;i<=top;i++)
            {
                printf("%d%c",num[i],(i==top?'\n':' '));
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000MS Memory Limit: 65536KB [Statistic][] [Discuss][] Problem

女爷i/ 2022年09月26日 03:51/ 0 赞/ 127 阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述请定一个无向图，顶点编号从0到n-1，用深度优

叁歲伎倆/ 2022年09月25日 06:28/ 0 赞/ 121 阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述请定一个无向图，顶点编号从0到

àì夳堔傛蜴生んèń/ 2022年08月14日 05:45/ 0 赞/ 147 阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Probl

妖狐艹你老母/ 2022年07月15日 06:25/ 0 赞/ 135 阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Descripti

深碍√TFBOYSˉ_/ 2022年07月12日 11:14/ 0 赞/ 98 阅读

相关图的深度遍历

Problem Description 请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。 Input 输入第一行

秒速五厘米/ 2022年07月12日 09:55/ 0 赞/ 113 阅读

相关图的深度遍历

Problem Description 请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。 Input 输

Myth丶恋晨/ 2022年07月12日 06:50/ 0 赞/ 114 阅读

相关图的深度遍历

Problem Description 请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。 Input 输

ゞ浴缸里的玫瑰/ 2022年07月12日 06:50/ 0 赞/ 152 阅读

相关图的深度遍历

图的深度遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Descripti

布满荆棘的人生/ 2022年06月10日 12:25/ 0 赞/ 135 阅读

相关图的深度遍历

> 深度优先搜索类似于树的前序遍历同样以如下连通图为例： ![连通图][SouthEast] 构建其对应的邻接表： ![对应邻接表][SouthEast 1]

秒速五厘米/ 2021年11月16日 14:46/ 0 赞/ 285 阅读