给定一个有向图G，对于任意一条有向边<Vi,Vj>，称Vi是Vj的直接前驱，Vj是Vi的直接后继，这种前驱与后继的关系具有传递性。
如果一个图的任何一个节点都具有反自反性，也就是说任何一个节点都不是自己的前驱或后继，那么这个有向图是拓扑有序的。
拓扑序列：
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：
若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。
注意：
①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
②若图中存在有向环，则不可能使顶点满足拓扑次序。
③一个DAG的拓扑序列通常表示某种方案切实可行。
拓扑排序的一个应用是可以有向图中是否存在有向环。如果一个有向图存在环，那么必然存在结点不具有反自反性，因而相应的拓扑有序序列是不存在的。。
拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
hdu 1285 确定比赛名次 链接：http://acm.hdu.edu.cn/showproblem.php?pid=1285
解法：拓扑排序，找到一个人，没人能赢他，或者能赢他的人都已经输出，即他的入度为0，则输出此人。注意重边。。。
代码：
View Code 
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 int n,m,sum;
6 int map[501][501],degree[501],a[501],b[501];
7 void topo(int x)
8 {
9 int i;
10 a[x]=1;
11 b[++sum]=x;
12 for(i=1;i<=n;i++)
13 if(!a[i]&&map[x][i])
14 degree[i]--;
15 }
16 int main()
17 {
18 int i,x,y;
19 while(~scanf("%d%d",&n,&m))
20 {
21 memset(map,0,sizeof(map));
22 memset(degree,0,sizeof(degree));
23 memset(a,0,sizeof(a));
24 for(i=0;i<m;i++)
25 {
26 scanf("%d%d",&x,&y);
27 if(map[x][y]==0)
28 {
29 map[x][y]=1;
30 degree[y]++;
31 }
32 }
33 sum=0;
34 while(sum<n)
35 {
36 for(i=1;i<=n;i++)
37 {
38 if(degree[i]==0&&a[i]==0)
39 {
40 topo(i);
41 break;
42 }
43 }
44 }
45 for(i=1;i<sum;i++)
46 printf("%d ",b[i]);
47 printf("%d\n",b[i]);
48 }
49 return 0;
50
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 int n,m,sum;
6 int map[501][501],degree[501],a[501],b[501];
7 void topo(int x)
8 {
9 int i;
10 a[x]=1;
11 b[++sum]=x;
12 for(i=1;i<=n;i++)
13 if(!a[i]&&map[x][i])
14 degree[i]--;
15 }
16 int main()
17 {
18 int i,x,y;
19 while(~scanf("%d%d",&n,&m))
20 {
21 memset(map,0,sizeof(map));
22 memset(degree,0,sizeof(degree));
23 memset(a,0,sizeof(a));
24 for(i=0;i<m;i++)
25 {
26 scanf("%d%d",&x,&y);
27 if(map[x][y]==0)
28 {
29 map[x][y]=1;
30 degree[y]++;
31 }
32 }
33 sum=0;
34 while(sum<n)
35 {
36 for(i=1;i<=n;i++)
37 {
38 if(degree[i]==0&&a[i]==0)
39 {
40 topo(i);
41 break;
42 }
43 }
44 }
45 for(i=1;i<sum;i++)
46 printf("%d ",b[i]);
47 printf("%d\n",b[i]);
48 }
49 return 0;
50
hdu 2094 产生冠军 链接：http://acm.hdu.edu.cn/showproblem.php?pid=2094
解法：这个跟上个题基本上一样，确定能不能产生冠军，能产生冠军即入度为0的点只有一个。也可以先用并查集来判断能不能形成连通图。
代码：
View Code 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 using namespace std;
6 int nu,m,sum;
7 int map[1001][1001];
8 int degree[1001];
9 char s[1001][51];
10 int a[1001];
11 int find(char *ss)
12 {
13 int i;
14 for(i=0;i<nu;i++)
15 {
16 if(strcmp(ss,s[i])==0)
17 return i;
18 }
19 strcpy(s[i],ss);
20 return nu++;
21 }
22 int topo()
23 {
24 int i,l=0;
25 for(i=0;i<nu;i++)
26 if(!degree[i])
27 l++;
28 return l;
29 }
30 int main()
31 {
32 char s1[101],s2[101];
33 int i,x,y;
34 while(~scanf("%d",&m))
35 {
36 if(m==0)
37 break;
38 nu=0;
39 memset(map,0,sizeof(map));
40 memset(degree,0,sizeof(degree));
41 memset(a,0,sizeof(a));
42 for(i=0;i<m;i++)
43 {
44 scanf("%s %s",s1,s2);
45 x=find(s1);
46 y=find(s2);
47 if(map[x][y]==0)
48 {
49 map[x][y]=1;
50 degree[y]++;
51 }
52 }
53 if(topo()==1)
54 puts("Yes");
55 else
56 puts("No");
57 }
58 return 0;
59
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 using namespace std;
6 int nu,m,sum;
7 int map[1001][1001];
8 int degree[1001];
9 char s[1001][51];
10 int a[1001];
11 int find(char *ss)
12 {
13 int i;
14 for(i=0;i<nu;i++)
15 {
16 if(strcmp(ss,s[i])==0)
17 return i;
18 }
19 strcpy(s[i],ss);
20 return nu++;
21 }
22 int topo()
23 {
24 int i,l=0;
25 for(i=0;i<nu;i++)
26 if(!degree[i])
27 l++;
28 return l;
29 }
30 int main()
31 {
32 char s1[101],s2[101];
33 int i,x,y;
34 while(~scanf("%d",&m))
35 {
36 if(m==0)
37 break;
38 nu=0;
39 memset(map,0,sizeof(map));
40 memset(degree,0,sizeof(degree));
41 memset(a,0,sizeof(a));
42 for(i=0;i<m;i++)
43 {
44 scanf("%s %s",s1,s2);
45 x=find(s1);
46 y=find(s2);
47 if(map[x][y]==0)
48 {
49 map[x][y]=1;
50 degree[y]++;
51 }
52 }
53 if(topo()==1)
54 puts("Yes");
55 else
56 puts("No");
57 }
58 return 0;
59
POJ 1094 Sorting It All Out 链接： http://poj.org/problem?id=1094
代码：
View Code 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 int n,m,j,i,q,flag1;
6 int map[100][100],degree[100],t[100],b[100];;
7 int topo()
8 {
9 int i,j,f=1,p,temp,k=0;
10 for(i=0;i<n;i++)
11 t[i]=degree[i];
12 for(i=0;i<n;i++)
13 {
14 p=0;
15 for(j=0;j<n;j++)
16 if(t[j]==0)
17 {
18 p++;
19 temp=j;
20 }
21 if(p==0)
22 return 0;
23 if(p>1)
24 f=-1;
25 b[k++]=temp;
26 t[temp]=-1;
27 for(j=0;j<n;j++)
28 if(map[temp][j]!=0)
29 t[j]--;
30 }
31 return f;
32 }
33 int main()
34 {
35 while(~scanf("%d %d",&n,&m))
36 {
37 flag1=0;
38 char c1,c2;
39 if(n==0&&m==0)
40 break;
41 memset(map,0,sizeof(map));
42 memset(degree,0,sizeof(degree));
43 for(i=0;i<m;i++)
44 {
45 scanf("%*c%c<%c",&c1,&c2);
46 map[c1-'A'][c2-'A']=1;
47 degree[c2-'A']++;
48 if(flag1==0)
49 q=topo();
50 if(q==1&&flag1==0)
51 {
52 printf("Sorted sequence determined after %d relations: ",i+1);
53 for(j=0;j<n;j++)
54 printf("%c",b[j]+'A');
55 printf(".\n");
56 flag1=1;
57 }
58 if(q==0&&flag1==0)
59 {
60 printf("Inconsistency found after %d relations.\n",i+1);
61 flag1=1;
62 }
63 }
64 if(flag1==0)
65 printf("Sorted sequence cannot be determined.\n");
66 }
67 return 0;
68
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 int n,m,j,i,q,flag1;
6 int map[100][100],degree[100],t[100],b[100];;
7 int topo()
8 {
9 int i,j,f=1,p,temp,k=0;
10 for(i=0;i<n;i++)
11 t[i]=degree[i];
12 for(i=0;i<n;i++)
13 {
14 p=0;
15 for(j=0;j<n;j++)
16 if(t[j]==0)
17 {
18 p++;
19 temp=j;
20 }
21 if(p==0)
22 return 0;
23 if(p>1)
24 f=-1;
25 b[k++]=temp;
26 t[temp]=-1;
27 for(j=0;j<n;j++)
28 if(map[temp][j]!=0)
29 t[j]--;
30 }
31 return f;
32 }
33 int main()
34 {
35 while(~scanf("%d %d",&n,&m))
36 {
37 flag1=0;
38 char c1,c2;
39 if(n==0&&m==0)
40 break;
41 memset(map,0,sizeof(map));
42 memset(degree,0,sizeof(degree));
43 for(i=0;i<m;i++)
44 {
45 scanf("%*c%c<%c",&c1,&c2);
46 map[c1-'A'][c2-'A']=1;
47 degree[c2-'A']++;
48 if(flag1==0)
49 q=topo();
50 if(q==1&&flag1==0)
51 {
52 printf("Sorted sequence determined after %d relations: ",i+1);
53 for(j=0;j<n;j++)
54 printf("%c",b[j]+'A');
55 printf(".\n");
56 flag1=1;
57 }
58 if(q==0&&flag1==0)
59 {
60 printf("Inconsistency found after %d relations.\n",i+1);
61 flag1=1;
62 }
63 }
64 if(flag1==0)
65 printf("Sorted sequence cannot be determined.\n");
66 }
67 return 0;
68
POJ 2367 Genealogical tree 链接： http://poj.org/problem?id=2367
代码：
View Code 1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5 const int N=102;
6 int degree[N],map[N][N],a[N],b[N];
7 int n,s;
8 void topo(int x)
9 {
10 int i;
11 a[x]=1;
12 b[++s]=x;
13 for(i=1;i<=n;i++)
14 {
15 if(!a[i]&&map[x][i])
16 {
17 degree[i]--;
18 }
19 }
20 }
21 int main()
22 {
23 int x,i;
24 scanf("%d",&n);
25 memset(a,0,sizeof(0));
26 memset(degree,0,sizeof(degree));
27 memset(map,0,sizeof(map));
28 for(i=1;i<=n;i++)
29 {
30 while(1)
31 {
32 scanf("%d",&x);
33 if(x==0)
34 break;
35 map[i][x]=1;
36 degree[x]++;
37 }
38 }
39 s=0;
40 while(s<n)
41 {
42 for(i=1;i<=n;i++)
43 {
44 if(degree[i]==0&&a[i]!=1)
45 {
46 topo(i);
47 }
48 }
49 }
50 for(i=1;i<n;i++)
51 printf("%d ",b[i]);
52 printf("%d\n",b[i]);
53 return 0;
54
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5 const int N=102;
6 int degree[N],map[N][N],a[N],b[N];
7 int n,s;
8 void topo(int x)
9 {
10 int i;
11 a[x]=1;
12 b[++s]=x;
13 for(i=1;i<=n;i++)
14 {
15 if(!a[i]&&map[x][i])
16 {
17 degree[i]--;
18 }
19 }
20 }
21 int main()
22 {
23 int x,i;
24 scanf("%d",&n);
25 memset(a,0,sizeof(0));
26 memset(degree,0,sizeof(degree));
27 memset(map,0,sizeof(map));
28 for(i=1;i<=n;i++)
29 {
30 while(1)
31 {
32 scanf("%d",&x);
33 if(x==0)
34 break;
35 map[i][x]=1;
36 degree[x]++;
37 }
38 }
39 s=0;
40 while(s<n)
41 {
42 for(i=1;i<=n;i++)
43 {
44 if(degree[i]==0&&a[i]!=1)
45 {
46 topo(i);
47 }
48 }
49 }
50 for(i=1;i<n;i++)
51 printf("%d ",b[i]);
52 printf("%d\n",b[i]);
53 return 0;
54
poj 3687 Labeling Balls 链接：http://poj.org/problem?id=3687
题意：n个重量分别为1-n的小球，给定一些小球间的重量关系。 在符合重量关系的前提下，先输出编号小的球。
分析：拓扑排序，倒着来，注意一下重边。。。
代码：
View Code 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 const int N=210;
6 int map[N][N],degree[N],a[N],b[N];
7 int n, m;
8 void topo()
9 {
10 int i,j;
11 memset(a,0,sizeof(a));
12 for(i=n;i>0;i--)
13 {
14 int q=-1;
15 for(j=n-1;j>=0;j--)
16 if(!a[j]&°ree[j]==0)
17 {
18 q=j;
19 break;
20 }
21 if(q==-1)
22 {
23 puts("-1");
24 return;
25 }
26 a[q]=1;
27 b[q]=i;
28 for(j=0;j<n;j++)
29 if(map[q][j])
30 degree[j]--;
31 }
32 for(i=0;i<n-1;i++)
33 printf("%d ",b[i]);
34 printf("%d\n",b[i]);
35 }
36 int main()
37 {
38 int t;
39 scanf("%d",&t);
40 while(t--)
41 {
42 int i;
43 scanf("%d%d",&n,&m);
44 memset(map,0,sizeof(map));
45 memset(degree,0,sizeof(degree));
46 for(i=0;i<m;i++)
47 {
48 int a,b;
49 scanf("%d%d",&a,&b);
50 a--;
51 b--;
52 if(!map[b][a])
53 degree[a]++;
54 map[b][a]=true;
55 }
56 topo();
57 }
58 return 0;
59
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 const int N=210;
6 int map[N][N],degree[N],a[N],b[N];
7 int n, m;
8 void topo()
9 {
10 int i,j;
11 memset(a,0,sizeof(a));
12 for(i=n;i>0;i--)
13 {
14 int q=-1;
15 for(j=n-1;j>=0;j--)
16 if(!a[j]&°ree[j]==0)
17 {
18 q=j;
19 break;
20 }
21 if(q==-1)
22 {
23 puts("-1");
24 return;
25 }
26 a[q]=1;
27 b[q]=i;
28 for(j=0;j<n;j++)
29 if(map[q][j])
30 degree[j]--;
31 }
32 for(i=0;i<n-1;i++)
33 printf("%d ",b[i]);
34 printf("%d\n",b[i]);
35 }
36 int main()
37 {
38 int t;
39 scanf("%d",&t);
40 while(t--)
41 {
42 int i;
43 scanf("%d%d",&n,&m);
44 memset(map,0,sizeof(map));
45 memset(degree,0,sizeof(degree));
46 for(i=0;i<m;i++)
47 {
48 int a,b;
49 scanf("%d%d",&a,&b);
50 a--;
51 b--;
52 if(!map[b][a])
53 degree[a]++;
54 map[b][a]=true;
55 }
56 topo();
57 }
58 return 0;
59