All Discs Considered(拓扑排序)

题意：有两个DVD，第一个DVD上有编号为1~n1的安装包，第二个DVD上有编号为n1+1~n1+n2的安装包，给出m组关系(a,b) 表示安装a之前必须先安装b。由于安装时每次只能插入一个DVD，问安装完所有的安装包，这两个DVD至少要交换插入多少次。ps:第一次插入算一次，最后一次拔出算一次。

思路：两次拓扑排序，以先插入第一个DVD，进行拓扑排序，求出交换次数；以先插入第二个DVD，进行拓扑排序，求出交换次数。最后输出这两种交换次数的最小的值。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 const int N=100005;
 6 int d[N],dd[N],head[N];
 7 int n1,n2,cnt;
 8 queue<int>q[2];
 9 struct node
10 {
11     int u,v,next;
12 } edge[N];
13 void init()
14 {
15     cnt = 0;
16     memset(head,-1,sizeof(head));
17     memset(d,0,sizeof(d));
18     memset(dd,0,sizeof(dd));
19 }
20 void add(int u,int v)
21 {
22     edge[cnt].u = u;
23     edge[cnt].v = v;
24     edge[cnt].next = head[u];
25     head[u] = cnt++;
26 }
27 inline void deal()
28 {
29     while(!q[0].empty()) q[0].pop();
30     while(!q[1].empty()) q[1].pop();
31     for (int i = 1; i <= n1+n2; i++)
32     {
33         if(dd[i]==0)
34         {
35             if(i <= n1)
36                 q[0].push(i);
37             else
38                 q[1].push(i);
39         }
40     }
41 }
42 int topsort(int k)
43 {
44     deal();
45     int ans = 0;
46     while(!q[k].empty()||!q[k^1].empty())
47     {
48         while(!q[k].empty())
49         {
50             int u = q[k].front();
51             q[k].pop();
52             for (int j=head[u]; j!=-1; j=edge[j].next)
53             {
54                 int v = edge[j].v;
55                 d[v]--;
56                 if(d[v]==0)
57                 {
58                     if(v<=n1)
59                         q[0].push(v);
60                     else
61                         q[1].push(v);
62                 }
63             }
64         }
65         ans++;
66         k^=1;
67     }
68     return ans;
69 }
70 int main()
71 {
72     int m,u,v;
73     while(~scanf("%d%d%d",&n1,&n2,&m))
74     {
75         if(n1==0&&n2==0&&m==0)
76             break;
77         init();
78         for (int i = 0; i < m; i++)
79         {
80             scanf("%d%d",&u,&v);
81             add(v,u);
82             dd[u]++;
83             d[u]++;
84         }
85         int ans1 = topsort(0);
86         for (int i = 1; i <= n1+n2; i++)
87             d[i] = dd[i];
88         int ans2 = topsort(1);
89         int ans=ans1<ans2?ans1:ans2;
90         printf("%d
",ans+1);
91     }
92     return 0;
93 }

View Code