【拓撲排序練習題】課程安排問題 curriculum

【問題描述】

一個軟體專業的學生必須學習一系列基本課程，其中有些課程是基礎課，它獨立於其它課程，如《高等數學》、《計算引論》；而另一些課程必須在學完作為它的基礎的先修課程才能開始。如，在《程序設計基礎》和《離散數學》學完之前就不能開始學習《資料結構》。這些先決條件定義了課程之間的領先（優先）關係。請你在符合上述領先（優先）條件的前提下，給出所有課程的一個有序序列，以方便學校排課。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n(0<n<=100)門課程

第2--n+1行分別表示第1--n門課程的先修課程資訊，每行有若干個整數m,s1,s2,...,sm

m表示該門課程有m門先修課程，s1,s2,...,sm分別表示m門先修課的編號，如果該門課沒有先修課程，則m為0。

【輸出格式】

一行，n個整數，表示n門課程編號的有序序列(如果這樣的序列不存在，則輸出no;如果有多個這樣的序列，輸出字典序最小的)

 

【輸入輸出樣例】

輸入文件名： curriculum.in

4

0

1 1

1 1

2 2 3

輸出文件名：curriculum.out

1 2 3 4

【分析】

裸代碼RawCode

C++语言: Codee#25679

01 /*
02 *Problem: 拓撲排序練習題 課程安排問題 curriculum
03 *Author: Yee-fan Zhu
04 *Website: http://zhuyf.tk/
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 #include <vector>
09 #include <algorithm>
10 using namespace std;
11 typedef vector<int> Vec;
12 typedef unsigned int usint;
13 int N;
14 const int MAXN=101;
15 Vec Map[MAXN];
16 int Zero[MAXN];
17 int Flag[MAXN];
18 Vec Res;
19
20 void init()
21 {
22     scanf("%d\n",&N);
23     int s;
24     int x;
25     for(int i=1;i<=N;i++)
26     {
27         scanf("%d",&s);
28         Zero[i]=s;
29         Flag[i]=0;
30         for(int j=1;j<=s;j++)
31         {
32             scanf("%d",&x);
33             Map[i].push_back(x);
34         }
35     }
36     for(int i=1;i<=N;i++)
37     {
38         sort(Map[i].begin(),Map[i].end());
39         //for(int j=0;j<Map[i].size();j++)
40     //        printf("%d ",Map[i][j]);
41         //printf("\n");
42     }
43 }
44
45 void solve()
46 {
47     int X;
48     int Out=0;
49     while(Out<N)
50     {
51         X=0;
52         for(int i=1;i<=N;i++)
53         {
54             if(Flag[i]==0 && Zero[i]==0)
55             {
56                 X=i;
57                 break;
58             }
59         }
60         if(X==0 && Out<N)
61         {
62             printf("no\n");
63             exit(0);
64         }
65        
66         /*Delete Edge*/
67         Vec::iterator iter;
68         for(int i=1;i<=N;i++)
69         {
70             iter=find(Map[i].begin(),Map[i].end(),X);
71             if(iter==Map[i].end())
72                 continue;
73             Map[i].erase(iter);
74             Zero[i]--;
75         }
76         //printf("%d ",X);
77         Res.push_back(X);
78         Flag[X]=1;
79         Out++;
80     }
81 }
82
83 int main()
84 {
85     freopen("curriculum.in","r",stdin);
86     freopen("curriculum.out","w",stdout);
87     init();
88     solve();
89     for(Vec::iterator iter=Res.begin();iter!=Res.end();iter++)
90         printf("%d ",*iter);
91     return 0;
92 }