poj2367 拓扑序

题意:有一些人他们关系非常复杂,一个人可能有很多后代,现在要制定一种顺序,按照前辈在后代前排列就行

拓扑序裸题,直接建边拓扑排序一下就行了。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 
 6 int ma[105][105],id[105],n;
 7 
 8 void topo(){
 9     queue<int>q;
10     for(int i=1;i<=n;++i)if(!id[i])q.push(i);
11     int cnt=0;
12     while(!q.empty()){
13         int u=q.front();
14         q.pop();
15         printf("%d",u);
16         if(++cnt==n)printf("
");
17         else printf(" ");
18         for(int i=1;i<=n;++i){
19             if(i!=u&&ma[u][i]){
20                 id[i]--;
21                 if(!id[i])q.push(i);
22             }
23         }
24     }
25 }
26 
27 int main(){
28     scanf("%d",&n);
29     for(int i=1;i<=n;++i){
30         int a;
31         while(scanf("%d",&a)&&a){
32             ma[i][a]=1;
33             id[a]++;
34         }
35     }
36     topo();
37     return 0;
38 }
View Code
原文地址:https://www.cnblogs.com/cenariusxz/p/4795221.html