编辑代码

#include<stdio.h>
#define N 100
int G[N][N],visited[N],path[N],cycle=-1,n;
void input(){
    printf("Please input matrix dimension:\n");
    scanf("%d",&n);
    printf("Please input matrix:\n");
    //示例
   /*不存在回路
    5
    0 1 0 1 1
    0 0 0 0 0
    1 1 0 1 0
    0 0 0 0 1
    0 0 0 0 0
   */
  /*存在回路0->1->4->3->0
  6
  0 1 0 0 1 1
  0 0 0 0 1 0
  0 1 0 1 0 0
  1 0 0 0 0 0
  0 0 0 1 0 1
  0 0 1 0 0 0
  */
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&G[i][j]);
        }
    }
}
int DFS(int i,int start){
    visited[i]=-1;
    path[i]=start;
    for(int j=0;j<n;j++){
        if(G[i][j]&&j!=start){
            if(visited[j]<0){
                cycle=i;
                return 0;
            }
            if(!DFS(j,i)){
                return 0;
            }
        }
    }
    visited[i]=1;
    return 1;
}
void DisPath(int i){
    if(i<0){
        return;
    }
    DisPath(path[i]);
    printf("%d",i);
    if(i>=0)
        printf("->");
}
int main(){
    input();
    int i;
    for(i=0;i<n;i++){
        if(!visited[i]&&!DFS(i,-1)){
            break;
        }
    }
    if(cycle<0){
        printf("Cycle non-existent!\n");
    }
    else{
        printf("Cycle existent!:\n");
        DisPath(cycle);
        printf("%d", i);
    }
    printf("\n");
    system("pause");
}