确定比赛名次（拓扑排序）

http://acm.hdu.edu.cn/showproblem.php?pid=1285

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16504 Accepted Submission(s): 6534

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3 1 2 2 3 4 3

Sample Output

1 2 4 3

题解：拓扑排序水题

给出代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 #define N 505
 8 #define M 250005
 9 int indegree[N];
10 struct Edge{
11     int to ;
12     //int v ;
13     int next;
14 }edge[M];
15 int head[N];
16 int Enct;
17 priority_queue <int,vector<int>,greater<int> > qu;//优先队列是按从大到小的顺序排列的，这样写改变排序方式从小到大 注意不要将两个尖括号连这写，因为连着写是一个运算符
18 void init()
19 {
20     Enct = 0 ;
21     memset(head,-1,sizeof(head));
22     while(!qu.empty()) qu.pop();//优先队列不可以用clear，
23 }
24 void add(int from, int to )
25 {
26     edge[Enct].to = to;
27     edge[Enct].next = head[from];
28     head[from] = Enct++;
29     indegree[to]++;
30 }
31 
32 
33 int main()
34 {
35     int n , m;
36     while(~scanf("%d%d",&n,&m))
37     {
38         init();
39         int a ,b;
40         for(int i = 0 ;i < m ; i++)
41         {
42             scanf("%d%d",&a,&b);
43             add(a, b);
44         }
45         int iq = 0;
46         for(int i = 1; i <= n ;i++)
47         {
48             if(indegree[i]==0)
49             {qu.push(i); iq++;}
50         }
51         for(int i = 0 ;i < iq ; i++)
52         {
53             int tm = qu.top();
54             if(i==0) printf("%d",tm);
55             else
56             printf(" %d",tm);//注意最后一个值后面没有空格
57             qu.pop();
58             for(int i = head[tm] ; i != -1 ; i = edge[i].next)
59             {
60                 Edge e = edge[i];
61                 indegree[e.to]--;
62                 if(indegree[e.to]==0)
63                 {
64                     qu.push(e.to);
65                     iq++;
66                 }
67             }
68         }
69         puts("");
70     }
71     return 0;
72 }

拓扑排序也可以用dfs写

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 #define N 505
 5  
 6 vector <int> ve[N];
 7 int c;
 8 int in[N];
 9 bool vis[N];
10 
11 int n;
12 void dfs()
13 {
14     for(int i = 1; i <= n; i++)
15     {
16         if(!vis[i] && in[i] == 0)
17         {
18             if(c++) printf(" ");
19             printf("%d", i);
20             vis[i] = 1;
21             int t = ve[i].size();
22             for(int j = 0; j < t; j++) in[ve[i][j]]--;
23             dfs();
24         }
25     }
26 }
27 int main()
28 {
29     int m;
30     while(~scanf("%d %d", &n, &m))
31     {
32         for(int i = 0; i <= n; i++) {ve[i].clear(); in[i] = 0; vis[i] = 0;}
33         int a, b;
34         for(int i = 0; i < m; i++)
35         {
36             scanf("%d %d", &a, &b);
37             ve[a].push_back(b);
38             in[b]++;
39         }
40         c = 0;
41         dfs();
42         puts("");
43     }
44     return 0;
45 }

下面再给出一个用链表写的dfs

各种方法自己领悟

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 #define N 505
 7 #define M 250005
 8 struct Edge{
 9     int to;
10     int next;
11 }edge[M];
12 int head[N];
13 int Enct;
14 int indegree[N];
15 int vis[N];
16 int c;
17 void init()
18 {
19     Enct = 0;
20     c = 0;
21     memset(head ,-1 , sizeof(head));
22     memset(indegree,0,sizeof(indegree));
23     memset(vis,0,sizeof(vis));
24 }
25 void add(int from , int to)
26 {
27     edge[Enct].to = to;
28     edge[Enct].next = head[from];
29     head[from] = Enct++;
30 }
31 int n;
32 void dfs()
33 {
34     for(int i = 1; i <= n ; i++)
35     {
36         if(!vis[i]&&indegree[i]==0)
37         {
38             vis[i] = 1;
39             if(c++) printf(" ");
40             printf("%d",i);
41             for(int j = head[i] ; j !=-1 ;j = edge[j].next)
42             {
43                 Edge e = edge[j] ;
44                 indegree[e.to]--;
45             }
46             dfs();//dfs放在这里是为了每次找到的输出顺序是从小到大的
47         }
48     }
49 }
50 int main()
51 {
52     int m;
53     while(~scanf("%d%d",&n,&m))
54     {
55         init();
56         int a , b;
57         for(int i = 0 ;i <m ;i++)
58         {
59             scanf("%d%d",&a,&b);
60             add(a,b);
61             indegree[b]++;
62         }
63         dfs();
64         puts("");
65     }
66     return 0;
67 }