voidfloyd(void){ for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (g[i][k] && g[k][j]) g[i][j]=1; }
Floyd判环
这是很懒的一种做法,只需求一遍传递闭包,然后看一看有没有自环既可。
时间复杂度O(n3)。(当然,用dfs可以O(n+m),只不过码量稍稍大一点。)
1 2 3 4 5 6 7 8 9 10 11 12
boolfloyd(void){ //Return 1 if circles exist. for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (g[i][k] && g[k][j]) g[i][j]=1; for (int i=1;i<=n;i++) if (g[i][i]) return1; return0; }