大意：判断是否有向图是否有环。
思路1：通过Floyd传递闭包来确定是否有向环。（350MS）
思路2：通过拓扑排序判断是否存在有向环。(109MS)
CODE1：
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; const int SIZE = 510; int G[SIZE][SIZE]; int n, m; int FLoyd() { for( int k = 0; k < n; k++) for( int i = 0; i < n; i++) for( int j = 0; j < n; j++) G[i][j] = G[i][j] ||(G[i][k] && G[k][j]); // if(G[i][k] && G[k][j]) G[i][j] = 1; for( int i = 0; i < n; i++) if(G[i][i] == 1) return 0; //存在环 return 1; } void init() { memset(G, 0, sizeof(G)); } int main() { while(~scanf( " %d%d ", &n, &m), n, m) { init(); while(m--) { int u, v; scanf( " %d%d ", &u, &v); G[u][v] = 1; } if(FLoyd()) { printf( " YES\n "); } else printf( " NO\n "); } return 0; }
CODE2：
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; const int SIZE = 510; int G[SIZE][SIZE]; int topo[SIZE], ind[SIZE]; int n, m; int toposort() { for( int i = 0; i < n; i++) { int u; for(u = 0; u < n; u++) if(!ind[u]) break; if(u >= n) return 0; topo[i] = u; ind[u]--; for( int v = 0; v < n; v++) if(G[u][v]) ind[v]--; } return 1; } void init() { memset(ind, 0, sizeof(ind)); memset(topo, 0, sizeof(topo)); memset(G, 0, sizeof(G)); } int main() { while(~scanf( " %d%d ", &n, &m), n, m) { init(); while(m--) { int u, v; scanf( " %d%d ", &u, &v); if(!G[u][v]) { G[u][v] = 1; ind[v]++; } } if(toposort()) { printf( " YES\n "); } else printf( " NO\n "); } return 0; }