#include<iostream> #include<cstring> using namespace std; const int MAXSIZE = 1010; int g[MAXSIZE][MAXSIZE]; bool vis[MAXSIZE]; // flag控制格式 int flag = 1; int n, m, s; //节点数，边数，起始节点编号 void dfs(int s); int main() { cin >> n >> m >> s; memset(g, 0, sizeof g); memset(vis, 0, sizeof vis); for (int i = 0; i < m;i++) { int a, b; cin >> a >> b; g[a][b] = g[b][a] = 1; } dfs(s); //检查是否所有节点都被访问过，判断是不是连通图，不是的话最后输出0 for (int i = 1; i <= n;i++) { if(vis[i]==0) { cout <<" "<< 0; break; } } return 0; } void dfs(int s) { if(flag!=1) cout << " "; //访问一个输出一个 cout << s ; flag = 0; vis[s] = 1; //注意顶点是从1开始的 for (int i = 1; i <= n;i++) { //如果没访问过并且有边 if(!vis[i]&&g[s][i]==1) { dfs(i); //原路返回时输出节点 cout << " " << s; flag = 0; } } }

这段代码是一个深度优先搜索（DFS）遍历无向图的程序。其中：

- 输入n代表节点数，m代表边数，s代表起始节点编号；
- 使用邻接矩阵g来表示图的连通性；
- 使用vis数组记录每个节点是否被访问过；
- 使用dfs函数进行深度优先搜索，从起始节点s开始，访问一个节点输出一个节点编号，并将vis数组对应位置设为1；
- 如果访问到一个未被访问过的相邻节点i，就递归调用dfs(i)进行搜索；
- 在返回时输出当前节点编号s，以表示搜索路径；
- 最后检查vis数组是否所有位置都为1，如果有未被访问过的节点则输出0，表示不是连通图。

相关问题

优化以下代码#include<iostream> using namespace std; #include<algorithm> #define MAXSIZE 100 int father[MAXSIZE];//存放父亲节点 typedef struct Mgraph { int s[MAXSIZE][MAXSIZE]; int n;//节点数 }; struct graph { int a, b, c; }arr[MAXSIZE]; bool compare(graph x, graph y) {//对边按照权值从小到大排序 return x.c < y.c; } int Find(int x) {//找到一个节点的根节点，并将其下面的所有节点的father都改为根节点。 while (x != father[x]) { int temp = x; x = father[x]; father[temp] = x; } return x; } int main() { Mgraph p; int m; cin >> p.n >> m; for (int i = 0; i < m; i++) { cin >> arr[i].a >> arr[i].b >> arr[i].c;//a,b间，需要c天 } for (int i = 1; i < p.n + 1; i++)//初始化father数组，将每个节点的父亲节点设置为自己 father[i] = i; sort(arr, arr + m, compare);//对边按照权值从小到大排序 for (int i = 0; i < m; i++) { if (Find(arr[i].a) != Find(arr[i].b)) father[Find(arr[i].a)] = Find(arr[i].b);//遍历每条边，如果该边的两个节点不在同一个连通块中，则将它们连通，并将它们的父亲节点设置为同一个节点。 if (Find(1) == Find(p.n)) {//如果1号节点和n号节点在同一个连通块中，则输出当前边的权值，并结束程序 cout << arr[i].c << endl; break; } } }

这段代码是 Kruskal 算法的实现，用于解决最小生成树问题。优化的方向可以从以下几个方面考虑：

1. 可以使用并查集的路径压缩优化，将 Find 函数中的路径压缩操作加上，可以有效降低时间复杂度。

2. 可以使用快读和快输来优化输入输出，加快读入和输出的速度。

3. 可以使用堆优化的 Kruskal 算法，将边按照权值建立小根堆，每次取出堆顶的边进行处理，可以降低时间复杂度。

4. 可以使用邻接表存储图，减小程序所占用的空间。

下面是代码的优化版：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;

#define MAXSIZE 100010

struct Edge {
    int u, v, w;
    bool operator < (const Edge& e) const {
        return w < e.w;
    }
};

int father[MAXSIZE];
int n, m;

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

int main() {
    scanf("%d%d", &n, &m);

    vector<Edge> edges(m);

    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }

    int ans = 0;

    for (int i = 0; i < m; i++) {
        int fu = find(edges[i].u);
        int fv = find(edges[i].v);

        if (fu == fv) {
            continue;
        }

        father[fu] = fv;
        ans = edges[i].w;

        if (find(1) == find(n)) {
            break;
        }
    }

    printf("%d\n", ans);

    return 0;
}

任务描述 任务：在本章实现的顺序表类中增加连接两个线性表的功能，即将线性表(a0, a1, …, an-1)和(b0, b1, …, bm-1)合并成一个线性表(a0, a1, …, an-1, b0, b1, …, bm-1)。顺序表类的用户可以使用表达式C=A+B将线性表A和B归并后存入线性表C。 编程要求 根据提示，在右侧编辑器补充代码，合并两个顺序表。 请根据输入创建两个顺序表，按要求合并之后，遍历输出归并后的顺序表。 测试说明 平台会对你编写的代码进行测试： 测试输入： 1 2 3 4 5 6； 预期输出： 1 2 3 4 5 6 测试输入： 1 45 990 1 23 9 78； 预期输出： 1 45 990 1 23 9 78 注意：使用c++，实现的数据结构为顺序表，顺序表的内容可能为空，空表的输入为null。

代码如下：

#include<iostream>
#include<cstring>
using namespace std;
#define MAXSIZE 1000

class SeqList{
    private:
        int data[MAXSIZE];
        int length;
        int maxsize;
    public:
        SeqList(int size = MAXSIZE){
            maxsize = size;
            length = 0;
        }
        int getLength(){
            return length;
        }
        bool isEmpty(){
            return length == 0;
        }
        bool isFull(){
            return length == maxsize;
        }
        bool insert(int index, int element){
            if(index < 0 || index > length || isFull()){
                return false;
            }
            for(int i = length; i > index; i--){
                data[i] = data[i-1];
            }
            data[index] = element;
            length++;
            return true;
        }
        bool remove(int index){
            if(index < 0 || index >= length || isEmpty()){
                return false;
            }
            for(int i = index; i < length-1; i++){
                data[i] = data[i+1];
            }
            length--;
            return true;
        }
        void clear(){
            length = 0;
        }
        bool set(int index, int element){
            if(index < 0 || index >= length || isEmpty()){
                return false;
            }
            data[index] = element;
            return true;
        }
        int get(int index){
            if(index < 0 || index >= length || isEmpty()){
                return -1;
            }
            return data[index];
        }
        void traverse(){
            for(int i = 0; i < length; i++){
                cout << data[i] << " ";
            }
            cout << endl;
        }
        SeqList operator+(const SeqList &list){
            SeqList newList;
            for(int i = 0; i < length; i++){
                newList.insert(i, data[i]);
            }
            for(int i = 0; i < list.getLength(); i++){
                newList.insert(length+i, list.get(i));
            }
            return newList;
        }
};

int main(){
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    SeqList list1(MAXSIZE), list2(MAXSIZE);
    int pos1 = 0, pos2 = 0;
    for(int i = 0; i < s1.length(); i++){
        if(s1[i] == ' '){
            int num = stoi(s1.substr(pos1, i-pos1));
            list1.insert(list1.getLength(), num);
            pos1 = i+1;
        }
    }
    int num = stoi(s1.substr(pos1, s1.length()-pos1));
    list1.insert(list1.getLength(), num);
    for(int i = 0; i < s2.length(); i++){
        if(s2[i] == ' '){
            int num = stoi(s2.substr(pos2, i-pos2));
            list2.insert(list2.getLength(), num);
            pos2 = i+1;
        }
    }
    num = stoi(s2.substr(pos2, s2.length()-pos2));
    list2.insert(list2.getLength(), num);
    SeqList list3 = list1 + list2;
    list3.traverse();
    return 0;
}