Computing composants fortement connectés en utilisant un langage de programmation c

Question

confus dans ce semgent code donc ce sont deux fonctions que je suppose buggy

void dfsloop1(int **g) 
{ 
    int i; 
    int temp=0; 
    for(i=0;i<875714;i++) 
    { 
     temp = f[i]; 
     x[temp-1] = i; 
    } 
    for(i=875714;i>0;i--) 
    { 
     if(!explored[x[i-1]]) 
     { 
      s = i-1; 
      dfs1(g,x[i-1]); 
     } 
    } 
} 

void dfs1(int **g,int i) 
{ 

    explored[i] = 1; 
    leader[i] = s; 
    int j; 
    for(j=0;j<a[i];j++) 
    { 
     if(!explored[(g[i][j]-1)]) 
     { 
      dfs1(g,g[i][j]); 
     } 
    } 
} 

tableau exploré ici est tenue de compte du noeud/vertex est cochée ou non si elle est cochée, alors ith vertex est cochée then explored[i-1] = 1 else explored[i-1] = 0,a[i] stocke le nombre de sommets i+1 par exemple par exemple le sommet n ° 1 est connecté à 2,4,5 puis a[0] sera 3, le graphique est passé dans la liste d'adjacence et J'ai déjà exécuté dfs sur le graphique inverse et enregistré cette numérotation magique dans f [i] en utilisant l'algorithme de kosaraju, maintenant je suis en train d'exécuter dfs sur mon graphique original g dans x [i] je stocke f [i] dans l'ordre croissant par exemple disons sur le 9 graphique de sommet f[0] = 7,f[1] = 3,f[2] = 1,f[4] = 2,f[5] = 5,f[6] = 9,f[7]=4,f[8] = 6 then x[0] = 2 (qui est l'indice du plus petit f[i]),x[1] = 4,x[2] = 1 etc.

Si j'ai laissé quelque chose ou quelque chose n'est pas clair s'il vous plaît faites le moi savoir. Merci

nombre total de sommets sont 875714

je suis nouveau sur stackoverflow donc si je l'ai fait quelque chose de mal me faire savoir

Merci

Answer 1

je considérais votre code. Je suppose que vous êtes nouveau dans ceci comme votre fonction principale est mélangée avec des codes qui n'est pas réellement commode.
Deux choses:
1. Vous avez affaire à des pointeurs et à des pointeurs.
2. Vous consommez plus de 10^5 entiers pour la variable/pointeur locale.

Je n'ai pas beaucoup de connaissances sur les pointeurs. Cependant, en tant que concurrent, j'avais l'habitude d'avoir une "erreur d'exécution" en déclarant localement une grande taille de tableau. Donc, je pense que votre problème réside dans ces deux sections. Essayez de déclarer globalement ces pointeurs de pointeur. Voir si ça aide. Je vous donne un lien de l'algorithme SCC. Je vous donne un lien de l'algorithme SCC.
e-maxx: https://e-maxx-eng.appspot.com/graph/strongly-connected-components.html

et ma mise en œuvre de scc:
https://bitbucket.org/techboy_zero/programming-and-software-development/src/035560584ce7ab7e0a3f6ab5ae1406095bd39b62/Programming%20Contest%20Algorithms/Graph%20Theory/Strongly_Connected_Component.cpp

Bien que, le mien est en C++. Juste voir les fonctions dfs et kosaraju. Si vous avez des difficultés à comprendre les mots clés, effectuez une recherche sur cplusplus.com. Si vous ne comprenez pas le mécanisme, n'hésitez pas à me demander.