ベクトルイテレータがインクリメントされていない

Question

dfs（CLRSに準拠）を使用してトポロジカルソートを実装しようとしています。必要な出力は表示されますが、プログラムはまだ実行され、セグメンテーション違反が発生します。デバッグのためのprintステートメントをほとんど使用しないで、forループが終了することはありませんが、それは（== Edges.end（））であるべきです。ただし、valgrindは、dfs（）内のエラーを

dfsVisit(it->first); 

に表示しています。私は何が欠けていますか？イテレータがインクリメントされず、forループが終了しないのはなぜですか？そして、なぜバンググラインドで異なる理由は？

#include<cstdio> 
#include<set> 
#include<list> 
#include<stack> 
#include<algorithm> 
#include<vector> 
#include<utility> 

struct node 
{ 
    int d, f, value; 
}; 

std::vector< std::pair<node, node> > Edges; 
std::vector< std::pair<node, node> >::iterator it; 
bool *visited; 
int N, myTime=0; 
node node1, node2; 
void dfsVisit(node); 

void dfs() 
{ 
    for(it=Edges.begin(); it!=Edges.end(); it++) 
     if(it->first.value<N) 
      if(!visited[it->first.value]) 
       dfsVisit(it->first); 
} 

void dfsVisit(node n) 
{ 
    myTime++;       //increment myTime 
    n.d=myTime;       //set the discovery time for node n 

    if(n.value<N) 
     if(visited[n.value]) 
      return; 

    for(it=Edges.begin(); it!=Edges.end(); ++it) 
    { 
     if(it->second.value>=N) 
      continue; 
     printf("In the for loop!\n"); 
     if(it->first.value==n.value && !visited[it->second.value]) 
     { 
      printf("it->first.value: %d\n",it->first.value+1); 
      printf("it->second.value: %d\n",it->second.value+1); 
      dfsVisit(it->second); 
      printf("Inside for and if\n"); 
     } 

     printf("Inside for but outside if!\n"); 
     printf("Edges.end()-it: %d\n",Edges.end()-it); 
    } 

    visited[n.value]=true; 
    myTime++; 
    n.f=myTime; 

    printf("For node %d, discovery time and finishing time is: %d, %d", n.value, n.d, n.f); 
    return; 
} 

int main() 
{ 
    int M, firstOfRule, secondOfRule, data, i; 
    //node node1, node2; 
    scanf("%d""%d",&N,&M); 
    visited=new bool[N]; 

    for(i=0;i<N;i++) 
     visited[i]=false; 

    while(M--) 
    { 
     scanf("%d",&firstOfRule); 
     scanf("%d",&secondOfRule); 

     while(secondOfRule--) 
     { 
      scanf("%d",&data); 
      node1.value=firstOfRule-1; 
      node2.value=data-1; 
      Edges.push_back(std::make_pair(node1,node2)); 
      printf("Pair: %d,%d\n", node1.value+1, node2.value+1); 
     } 
    } 

    for(std::vector< std::pair<node, node> >::const_iterator it=Edges.begin(); it!=Edges.end(); ++it) 
     printf("Connected %d and %d\n",it->first.value+1,it->second.value+1); 

    dfs(); 

    return 0; 
} 

出力ファイルは以下の通りである：あなたの助けのための

Pair: 1,2 
Pair: 2,3 
Connected 1 and 2 
Connected 2 and 3 
In the for loop! 
it->first.value: 1 
it->second.value: 2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 2 
In the for loop! 
it->first.value: 2 
it->second.value: 3 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: 1 
For node 2, discovery time and finishing time is: 3, 4Inside for and if 
Inside for but outside if! 
Edges.end()-it: 0       //-----> Why doesn't it exit here? 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -1 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -2 
In the for loop! 
Inside for but outside if! 
Edges.end()-it: -3 
... and so on until the program crashes! 

ありがとう！

Answer 1

グローバル変数としてstd::vector< std::pair<node, node> >::iterator it;を宣言しました。

ただし、再帰関数dfsVisitで使用しています。これは、dfsVisitへのネストされたコールが終了すると、it == Edges.end()を残すことを意味します。しかし、より前のdfsVisitは、ループを実行し続け、未定義の動作を引き起こす++itを実行します。

これを修正するには、itをdfsVisit関数のローカル変数にします。

メモ：コンパイラがC++ 11をサポートしている場合は、タイピングを避けることができ、autoを使用してイテレータを宣言できます。