poj1236

题目大意：给出一个各个学校之间的单向连通图，任务A：求出要令所有学校都收到软件的最小接收学校数目；任务B：求出至少需要添加多少条边，令无论将软件发布到哪一个学校，每一个学校都可以接收到软件

思路：对单向图求强连通分量，缩点，对于缩点后的图：求出入度为0的缩点个数，这是任务A；求出入度为0和出度为0的缩点个数，取较大的数，这是任务B。

可能有人问，为什么任务A不是直接求出强连通分量的个数，而是求出入度为0的缩点数呢？因为一个缩点，若入度不为0，则它一定可以从其他缩点得到软件，而不需要发一份给它。对于任务B，则要求添加尽可能少的边，使图成为全连通图，假设有一缩点u，它的出度为0，若将软件发布到这个缩点，则一定不能使得所有学校都收到软件（当然，有一个例外，就是一开始的图就已经是全连通的）。我们需要做的是：将出度为0的缩点全部连接到入度为0的缩点，这样到最后一定可以使得图成为全连通图。因此，对于出度为0和入度为0的缩点个数，取较大的输出就是任务B了。

注意：当图一开始就是全连通的，应该输出：1 0

View Code

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 const int maxn=105;
 6 vector <int> a[maxn];
 7 
 8 int n;
 9 int real[maxn],low[maxn],stack[maxn],depth,total,top;
10 bool instack[maxn];
11 int color[maxn];
12 bool f1[maxn],f2[maxn];
13 
14 void dfs(int u)
15 {
16      int v;
17      real[u]=low[u]=++depth;
18      stack[++top]=u;
19      instack[u]=true;
20      for (int i=0;i<a[u].size();i++)
21      {
22          v=a[u][i];
23          if (!real[v])
24          {
25                       dfs(v);
26                       low[u]=min(low[u],low[v]);
27          }
28          else if (instack[v])
29               low[u]=min(low[u],real[v]);
30      }
31      
32      if (real[u]==low[u])
33      {
34                          total++;
35                          while (stack[top+1]!=u)
36                          {
37                                v=stack[top--];
38                                color[v]=total;
39                                instack[v]=false;
40                          }
41      }
42 }
43 
44 void tarjan()
45 {
46      memset(real,0,sizeof(real));
47      memset(instack,false,sizeof(instack));
48      memset(stack,0,sizeof(stack));
49      depth=total=top=0;
50      for (int i=1;i<=n;i++)
51          if (!real[i])
52             dfs(i);
53 }
54 
55 void solve()
56 {
57      if (total==1)
58      {
59                   cout<<"1"<<endl<<"0"<<endl;
60                   return;
61      }
62      memset(f1,false,sizeof(f1));
63      memset(f2,false,sizeof(f2));
64      for (int i=1;i<=n;i++)
65      {
66          for (int j=0;j<a[i].size();j++)
67              if (color[i]!=color[a[i][j]])
68              {
69                                           f1[color[i]]=true;
70                                           f2[color[a[i][j]]]=true;
71              }
72      }
73      int result1=0,result2=0;
74      for (int i=1;i<=total;i++)
75      {
76          if (!f2[i]) result1++;
77          if (!f1[i]) result2++;
78      }
79      cout<<result1<<endl<<max(result1,result2)<<endl;
80 }
81 
82 int main()
83 {
84     cin>>n;
85     int m;
86     for (int i=1;i<=n;i++)
87     {
88         a[i].clear();
89         cin>>m;
90         while (m!=0)
91         {
92               a[i].push_back(m);
93               cin>>m;
94         }
95     }
96     tarjan();
97     solve();
98     return 0;
99 }