图的深度遍历

秒速五厘米 2022-07-12 09:55 138阅读 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  
Hint

Author

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int a[110][110];//邻接矩阵
    _Bool visit[10010];
    void dfs(int x, int k)
    {
        visit[x] = 1;//标记已经走过
        int i;
        for(i = 0; i < k; i++)
        {
            if(!visit[i] && a[x][i])//从第一个开始找
            {
                printf(" %d", i);
                dfs(i, k);//递归调用
            }
        }
    }
    int main()
    {
        int n, m, k, u, v, i;
        scanf("%d", &n);
        while(n--)
        {
            memset(a, 0, sizeof(a));
            memset(visit, 0, sizeof(visit));
            scanf("%d%d", &k, &m);
            for(i = 0; i < m; i++)
            {
                scanf("%d%d", &u, &v);
                a[u][v]++;
                a[v][u]++;//无向
            }
            printf("%d", 0);
            dfs(0, k);
            printf("\n");
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关图的深度遍历

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

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

相关图的深度遍历

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

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

相关图的深度遍历

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

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

相关图的深度遍历

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

冷不防/ 2022年08月10日 06:08/ 0 赞/ 32 阅读

相关图的深度遍历

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

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

相关图的深度遍历

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

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

相关图的深度遍历

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

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

相关图的深度遍历

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

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

相关图的深度遍历

think: 1题目可以邻接矩阵存储，如果用邻接表得需要将邻接表进行有序化，自己一开始没有用有序化邻接表，根据推算自己的样板数据应该并不通过，但样本数据竟然对了，当然提交O

Dear 丶/ 2022年07月12日 06:49/ 0 赞/ 67 阅读

相关图的深度遍历

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

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