c++ - 在无向图中查找连接组件的数量

Question

用户输入顶点数 (n)，然后 - 在接下来的 n 行中 - 顶点是如何连接的，即数 x i 行中的 表示顶点 i 与顶点 x 相连(该图是无向的)。任务是找到这个图中连接的组件的数量，而我的代码 - 由于某种原因我无法找到 - 输出错误的值(例如，输入 4 2 1 2 4 ，我的代码输出 4 而不是 2)。非常感谢任何帮助。

#include <iostream>
#include <vector>
#include <stack>

int n;

using namespace std;
vector <int> graph[1000006];
int components[1000006];
int no_of_components;
stack <int> mystack;

int main(){

    cin >> n;

    for (int i=0; i<n; i++){
        int X;
        cin >> X;
        graph[X-1].push_back(i);
    }

    for (int i=0; i<n; i++){

        if (components[i]>0) continue;

        no_of_components++;

        mystack.push(i);
        components[i]=no_of_components;

        while (mystack.empty()==false){
            int v;

            v=mystack.top();
            mystack.pop();

            for (int u=0; u<graph[v].size(); u++){
                if (components[u]>0) continue;

                mystack.push(u);
                components[u]=no_of_components;

            }
        }
    }

    cout << no_of_components;

    return 0;

}

Answer 1

在您的代码中，允许您遍历节点 v 的连接的计数器 u 与连接本身之间存在混淆:

• v是一个节点
• graph[v] 是连接 vector
• u 是连接 vector 中的索引
• 所以 graph[v][u] 是连接到 v 和 component[graph[v][u]] 的节点您必须更新的组件标记

因此您必须按如下方式更正内部 for 循环:

        for (int u=0; u<graph[v].size(); u++){
            if (components[graph[v][u]]>0) continue;

            mystack.push(graph[v][u]);
            components[graph[v][u]]=no_of_components;

        }

然后按预期工作。

Online demo