图的深度遍历

布满荆棘的人生 2022-06-10 12:25 139阅读 0赞

图的深度遍历  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
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<bits/stdc++.h>
    
    using namespace std;
    
    bool Vis[100];
    bool Map[100][100];
    int k;
    
    void DFS(int i)
    {
        if(i == 0)
            cout<<i;
        else
            cout<<" "<<i;
        Vis[i] = 1;
        for(int j = 0; j < k; j++)
        {
            if(!Vis[j]&&Map[i][j] == 1)//没有访问过且有联通
                DFS(j);
        }
    }
    
    int main()
    {
        int n,u,v,m;
        while(cin>>n)
        {
            while(n--)
            {
                cin>>k>>m;
                memset(Vis,0,sizeof(Vis));
                memset(Map,0,sizeof(Map));
                while(m--)
                {
                    cin>>u>>v;
                    Map[u][v] = Map[v][u] = 1;
                }
                for(int i = 0; i < k; i++)
                {
                    if(!Vis[i])
                        DFS(i);
                }
                cout<<endl;
            }
        }
        return 0;
    }
    
    
    
    
    /***************************************************
    Result: Accepted
    Take time: 0ms
    Take Memory: 164KB
    Submit time: 2017-02-20 15:22:16
    ****************************************************/