求无向图的连所有通分量

Question

问题遇到的现象和发生背景

输入一个无向图，输出所有连通分量。

【输入形式】

输入一个无向图，第一行为两个正整数n和m，1≤n≤100，1≤m≤500，分别表示顶点数和边数，顶点序号从1开始计起；第二行为m个正整数对“a b”，用空格隔开，表示顶点a和顶点b之间有一条边。每条边出现一次且仅一次，图中不存在自身环和平行边。

测试数据保证无向图不会出现孤立顶点。

【输出形式】

如果无向图包含w个连通分量，则输出w行，每行按升序输出一个连通分量中的各个顶点的序号，用空格隔开。按字典序输出各个连通分量，即按每个连通分量包含的最小顶点序号的升序输出各个连通分量。

【样例输入】

6 6

1 2

2 3

3 1

4 5

5 6

6 4

【样例输出】

1 2 3

4 5 6

问题相关代码，请勿粘贴截图

#include<bits/stdc++.h>
using namespace std;
int n,m;
int height[1000];
int d[1000][1000];
void floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                }
            }
}
void change(int j)
{
    for(int i=0;i<n;i++)
    {
        d[j][i]=9999;
    }
}
bool judgeAll(int j)
{
    for(int i=0;i<n;i++)
    {
        if(d[j][i]!=9999)
            return false;
    }
    return true;
}
int main()
{
        cin>>n>>m;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                d[i][j]=9999;
        for(int i=0;i<m;i++)
        {
            int x,y;
            cin>>x>>y;
            d[x-1][y-1]=1;
            d[y-1][x-1]=1;
        }
        floyd();
//        for(int i=0;i<n;i++)
//        {
//            for(int j=0;j<n;j++)
//                    cout<<d[i][j];
//            cout<<endl;
//        }
        string s[1000];int k=0;
//        for(int i=0;i<n;i++)
//        {
//            if(judgeAll(i))
//            {
//                s[k]+=char(i+'1');
//                s[k]+=' ';
//                k++;
//            }
//        }
        for(int i=0;i<n;i++)
        {
            int flag=0;
            for(int j=0;j<n;j++)
            {
                if(d[i][j]!=9999&&i!=j)
                {
                    change(j);
                    s[k]+=char(j+'1');
                    s[k]+=' ';
                    flag=1;
                }
                else if(d[i][j]!=9999&&i==j)
                {
                    s[k]+=char(j+'1');
                    s[k]+=' ';
                    flag=1;
                }
            }
            if(flag==1)
                k++;

        }
        sort(s,s+k);
        for(int i=0;i<k;i++)
            cout<<s[i]<<endl;
        return 0;
}

运行结果及报错内容

我的解答思路和尝试过的方法

我想的是利用floyd算法求出每个顶点间的最短路径，然后对求得的最短路径矩阵判断，连通的一定在最短路径中是可达的
然后，只用对最短路径矩阵进行判断即可

我想要达到的结果

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。