输入数据：
4 6
1 2
1 3
2 3
3 4
2 4
4 2
4 6
1 2
1 3
2 3
3 4
2 4
1 2
topo排序为偏序：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int indegree[] ;
queue<int>q;
int n , m ;
bool map[][] ;
int a[] ;
int topo(int n)
{
int cnt = ;
while (!q.empty ())
q.pop () ; for(int i = ; i <= n ; i++) {
if (indegree[i] == ) {
q.push(i);//入度为0的点为起始点
}
} int temp ;
while(!q.empty()) {
temp = q.front();
a[cnt ++] = temp ;
q.pop();
for(int i = ; i <= n ; i++) {
if(map[temp][i]) {
indegree[i]--;
if(indegree[i] == )
q.push(i);
}
}
}
if (cnt == n) //当输出的顶点数小于图中的顶点数时，输出有回路信息
for (int i = ; i < n ; i++) {
printf ("%d----->" , a[i]) ;
}
else
puts ("The network has a cycle!") ;
} int main ()
{
// freopen ("a.txt" , "r" , stdin) ;
int u , v ;
while (~ scanf ("%d%d" , &n , &m)) {
memset (indegree , , sizeof(indegree)) ;
memset (map , , sizeof(map)) ;
for (int i = ; i < m ; i++) {
scanf ("%d%d" , &u , &v) ;
if (!map[u][v])//在u 和 v 没有连通时
indegree[v]++ ;//点v的入度++
map[u][v] = ;//表示连通
}
topo (n) ;
}
}
演示：http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/topological_sort.asp
详细：http://blog.csdn.net/dm_vincent/article/details/7714519
-----------------hash table------------------------------------
struct Hash
{
int nxt ;
ll w ;
Hash () {}
Hash (int nxt , ll w) : nxt (nxt) , w (w) {}
}e[M];
int H[M] , E ; void init ()
{
E = ;
memset (H , , sizeof(H) ) ;
} void Insert (ll x)
{
int y = x % M ;
if (y < ) y += M ;
e[E ++] = (H[y] , x) ;
H[y] = E ;
} bool Find (ll x)
{
int y = x % M ;
if (y < ) y += M ;
for (int i = H[y] ; i ; i = e[i].nxt) {
if (e[i].w == x) return true ;
}
return false ;
}
------------------邻接表--------------------------------------------------------
struct edge
{
int u , v , w , nxt ;
edge () {}
edge (int u , int v , int w , int nxt) : u (u) , v (v) , w (w) , nxt (nxt) {}
}e[M];
int H[M] , E ;
void init ()
{
memset (H , , sizeof(H) ) ;
E = ;
} void addedge ()
{
e[E ] = edge (u , v , w , H[u]) ;
H[u] = E ++;
e[E ] = edge (v , u , w , H[v]) ;
H[v] = E ++;
}
用邻接表优化后的。时间，空间复杂度都降为O(N)