2107 数据结构实验之图论二：图的深度遍历

叁歲伎倆 2022-07-14 04:40 69阅读 0赞

[数据结构实验之图论二：图的深度遍历][Link 1]

#include <iostream>  
    #include <cstdlib>  
    #include <cstring>  
    int sum;
    using namespace std;  
    
    int vis[100];  
    int dis[100];  
    int map[100][100];  
    int k;  
    
    void DFS(int t)  
    {  
    
        vis[t] = 1;                     // 标记已被访问过  
        dis[sum++]=t;
        for(int j=0; j<k; j++)          // 寻找邻接点  
        {  
            if(!vis[j] && map[t][j]==1) // 此顶点没被访问过且两点有边相连接  
                DFS(j);  
        }  
    }  
    
    int main()  
    {  
        int m,t;  
        int u,v;  
        int i,j;  
        cin>>t;  
        while(t--)  
        {  
            cin>>k>>m;  
             sum=0;
            memset(vis,0,sizeof(vis));  
            memset(map, 0, sizeof(map));  
             memset(dis, 0, sizeof(dis));  
            for (i=0; i<m; i++)  
            {  
                cin>>u>>v;  
                map[u][v] = map[v][u] = 1;  
            }  
    
            for(i=0; i<k; i++)     // K 个顶点 编号为0~k-1  
            {  
                if(!vis[i])        // 如果此顶点没被访问过，则进行DFS深搜  
                    DFS(i);  
            }  
             for(i=0;i<k-1;i++)
                 cout<<dis[i]<<" ";
            cout<<dis[i]<<endl;
        }  
        return 0;  
    }

[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2228/pid/2107