编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <conio.h>
#define N 100
int G[N][N];

int path[N], visited[N], n, cycle;
void input(){
    //输入矩阵
    memset(G, 0, sizeof(G));
    memset(visited, 0, sizeof(visited));
    memset(path, 0, sizeof(path));
    printf("输入矩阵维度:\n");
    scanf("%d",&n);
    printf("请输入 %d * %d 矩阵(1=存在弧,0=不存在弧):\n",n,n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&G[i][j]);
        }
    }
}
int DFS(int u, int start){
	visited[u] = -1; //标记为被访问
	path[u] = start; //1=有路径,-1=没有路径
	for (int i = 0; i < n;i++){
		if (G[u][i]&&i!=start){
			if (visited[i]<0){
                //如果节点已经被访问过
				cycle = u;
				return 0;
			}
			if (!DFS(i,u)){
                //递归
				return 0;
			}
		}
	}
	visited[u] = 1; //标记为访问
	return 1; //
}

void DisPath(int u){
    //递归
	if (u<0)
	{
		return;
	}
	DisPath(path[u]);
    printf("%d ",u);

}

void main(){
	input();
	cycle = -1;
	for (int i = 0; i < n;i++)
	{
		if (!visited[i]&&!DFS(i,-1))//  //如果没被访问过而且
		{
			break;

		}
	}
	if (cycle<0)
	{
        printf("不存在环!");
	}
	else
	{
		printf("存在环!\n");
		DisPath(cycle);
		printf("\n");
	}
}