1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<conio.h>
#define NBR_NOEUD 100
short int noeudDejaVisite[NBR_NOEUD];
int noeudAdjacent[NBR_NOEUD][NBR_NOEUD];
short int indicesAdjacent[NBR_NOEUD];
short int marqueur[NBR_NOEUD];
int nbrNoeud,nbrArcs;
void lireForet(){
int curArc;
printf("entrez le nombre de chemins:");
scanf("%d",&nbrArcs);
printf("entrez le nombre d'intersections:");
scanf("%d",&nbrNoeud);
printf("entrez les divers chemins:\n");
for(curArc=0;curArc<nbrArcs;curArc++)
{
int depart,arrivee;
scanf("%d%d",&depart,&arrivee);
noeudAdjacent[depart][indicesAdjacent[depart]++] = arrivee;
}
}
int verifieCycle(int cle)
{
int curNoeud;
if( marqueur[cle] )
return 1;
if( noeudDejaVisite[cle] )
return 0;
noeudDejaVisite[cle] = marqueur[cle] = 1;
for(curNoeud =0;curNoeud<indicesAdjacent[cle] ;curNoeud++)
if( verifieCycle( noeudAdjacent[cle][curNoeud] ) )
return 1;
marqueur[cle] = 0;
return 0;
}
int main(){
int curNoeud;
clrscr();
lireForet();
for(curNoeud=1;curNoeud<=nbrNoeud;curNoeud++)
if( noeudDejaVisite[curNoeud] == 0 )
if( verifieCycle(curNoeud) )
{
printf("OUI il y'a un cycle");
getch();
return 0;
}
printf("NON il n'a pas de cycle");
getch();
return 0;
} |
Partager