1

ユーザーは頂点の数 ( n ) を入力し、次に - 次のn行で - 頂点がどのように接続されているかを入力します。つまり、i番目の行の番号xは、頂点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;

}
4

1 に答える 1

0

あなたのコードではu、ノード v の接続を反復処理できるようにするカウンターと、接続自体との 間に混乱があります。

  • vノードです
  • graph[v]接続のベクトルです
  • u接続のベクトルのインデックスです
  • 接続されて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;

        }

その後、期待どおりに動作します。

オンラインデモ

于 2016-02-19T18:44:30.417 に答える