Description
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
Input
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
1
2
Source
題目大意：N(2<N<100)各學校之間有單向的網(wǎng)絡，每個學校得到一套軟件后，可以通過單向網(wǎng)絡向周邊的學校傳輸，問題1：初始至少需要向多少個學校發(fā)放軟件，使得網(wǎng)絡內所有的學校最終都能得到軟件。2，至少需要添加幾條傳輸線路(邊)，使任意向一個學校發(fā)放軟件后，經過若干次傳送，網(wǎng)絡內所有的學校最終都能得到軟件。
具體算法：先用Korasaju Algorithm求出有向圖所有的強連通分量，然后將所有的強連通分量縮成一個點(縮點)，這樣原來的有向圖就縮成了一個DAG圖(有向無環(huán)圖)；用2個數(shù)組分別記錄新生成的DAG圖中的每個頂點(包括原來的頂點和強連通分量的縮點)是否有出邊和入邊，最后遍歷每個頂點，如果沒有入邊，則ans1++；如果沒有出邊，ans2++。最后所求即為ans1和max(ans1,ans2)。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 101;
int n,m,cnt;
bool visit[MAXN];
int set[MAXN],order[MAXN],in[MAXN],out[MAXN];
vector< vector<int> > adj;
vector< vector<int> > radj;
void dfs(int u)
{
visit[u]=true;
int i,len=adj[u].size();
for(i=0;i<len;i++)
if(!visit[adj[u][i]])
dfs(adj[u][i]);
order[cnt++]=u;
}
void rdfs(int u){
visit[u]=true;
set[u]=cnt;
int i,len=radj[u].size();
for(i=0;i<len;i++)
if(!visit[radj[u][i]])
rdfs(radj[u][i]);
}
void korasaju(){
int i;
memset(visit,false,sizeof(visit));
for(cnt=0,i=1;i<=n;i++)
if(!visit[i])
dfs(i);
memset(visit,false,sizeof(visit));
for(cnt=0,i=n-1;i>=0;i--)
if(!visit[order[i]])
cnt++,rdfs(order[i]);
}
int main(){
int i,j;
scanf("%d",&n);
adj.assign(n+1,vector<int>());
radj.assign(n+1,vector<int>());
for(i=1;i<=n;i++){
while(scanf("%d",&m),m){
adj[i].push_back(m);
radj[m].push_back(i);
}
}
korasaju();
memset(in,1,sizeof(in));
memset(out,1,sizeof(out));
for(i=1;i<=n;i++)
for(j=0;j<adj[i].size();j++)
if(set[i]!=set[adj[i][j]]){
out[set[i]]=0;
in[set[adj[i][j]]]=0;
}
int ans1=0,ans2=0;
for(i=1;i<=cnt;i++){
if(out[i]) ans2++;
if(in[i]) ans1++;
}
if(cnt==1){
printf("1\n");
printf("0\n");
}
else{
printf("%d\n",ans1);
printf("%d\n",max(ans1,ans2));
}
return 0;
}