题目链接：确定比赛名次
题目分析：若P1赢了P2，则在连一条边P1-->p2，对所有结点排序，求得一个序列，使得每一条有向边(u, v)对应的u都排在v的前面
方法一：
dfs，白书上讲的方法，但该方法不能保证输入的顺序 vis[u]=0表示从来没有访问过（从来没有调用过dfs(u)）；
vis[u]=1表示已经访问过，并且还递归访问过它的所有子孙（即dfs(u)曾被调用过，并已返回）；这表示u已经包含在一个拓扑排序当中
c[u]=-1表示正在访问（即递归调用dfs(u)正在栈帧中，尚未返回），这表明有一个环，不满足拓扑排序，返回一个错误
#include <stdio.h> #include <memory.h> const int maxn=500+5; int n,g[maxn][maxn],vis[maxn],st[maxn],cnt; void init() { cnt=n; memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); } bool dfs(int u) { vis[u]=-1; for(int v=1;v<=n;v++){ if(g[u][v]){ if(vis[v]==-1)return false; if(!vis[v]&&!dfs(v))return false; } } vis[u]=1; st[--cnt]=u; return true; } bool toposort() { for(int u=1;u<=n;u++){ if(!vis[u]) if(!dfs(u))return false; } return true; } int main() { freopen("in.txt","r",stdin); int m,p1,p2; while(scanf("%d %d",&n,&m)!=EOF){ init(); while(m--){ scanf("%d %d",&p1,&p2); g[p1][p2]=1; } if(toposort()){ for(int i=0;i<n-1;i++)printf("%d ",st[i]); printf("%d\n",st[n-1]); } } return 0; }方法二：
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
代码：
#include <stdio.h> #include <memory.h> const int maxn=500+5; int n,deg[maxn],st[maxn],cnt; bool g[maxn][maxn]; void init() { cnt=n; memset(g,0,sizeof(g)); memset(deg,0,sizeof(deg)); } void toposort() { int cur; for(int i=0;i<n;i++){ for(int u=1;u<=n;u++){ if(!deg[u]){ cur=u; deg[u]--; st[i]=cur; break; } } for(int v=1;v<=n;v++){ if(g[cur][v]){ g[cur][v]=false; deg[v]--; } } } } int main() { //freopen("in.txt","r",stdin); int m,p1,p2; while(scanf("%d %d",&n,&m)!=EOF){ init(); while(m--){ scanf("%d %d",&p1,&p2); if(!g[p1][p2]){ g[p1][p2]=true; deg[p2]++; } } toposort(); for(int i=0;i<n-1;i++)printf("%d ",st[i]); printf("%d\n",st[n-1]); } return 0; }