這個(gè)結(jié)合上題，類似的代碼解決的：http://www.cnblogs.com/kuangbin/archive/2011/08/07/2130062.html
Network of Schools
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 5354 |
|
Accepted: 2106 |
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
強(qiáng)連通分量縮點(diǎn)求入度為0的個(gè)數(shù)和出度為0的分量個(gè)數(shù)
題目大意：N(2<N<100)各學(xué)校之間有單向的網(wǎng)絡(luò)，每個(gè)學(xué)校得到一套軟件后，可以通過(guò)單向網(wǎng)絡(luò)向周邊的學(xué)校傳輸，問(wèn)題1：初始至少需要向多少個(gè)學(xué)校發(fā)放軟件，使得網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。2，至少需要添加幾條傳輸線路(邊)，使任意向一個(gè)學(xué)校發(fā)放軟件后，經(jīng)過(guò)若干次傳送，網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。
也就是：
? 給定一個(gè)有向圖，求：
1) 至少要選幾個(gè)頂點(diǎn)，才能做到從這些頂點(diǎn)出發(fā)，可以到達(dá)全部頂點(diǎn)
2) 至少要加多少條邊，才能使得從任何一個(gè)頂點(diǎn)出發(fā)，都能到達(dá)全部頂點(diǎn)
? 頂點(diǎn)數(shù)<= 100
解題思路：
? 1. 求出所有強(qiáng)連通分量
? 2. 每個(gè)強(qiáng)連通分量縮成一點(diǎn)，則形成一個(gè)有向無(wú)環(huán)圖DAG。
? 3. DAG上面有多少個(gè)入度為0的頂點(diǎn)，問(wèn)題1的答案就是多少
在DAG上要加幾條邊，才能使得DAG變成強(qiáng)連通的，問(wèn)題2的答案就是多少
加邊的方法：
要為每個(gè)入度為0的點(diǎn)添加入邊，為每個(gè)出度為0的點(diǎn)添加出邊
假定有 n 個(gè)入度為0的點(diǎn)，m個(gè)出度為0的點(diǎn)，如何加邊？
把所有入度為0的點(diǎn)編號(hào) 0,1,2,3,4 ....N -1
每次為一個(gè)編號(hào)為i的入度0點(diǎn)可達(dá)的出度0點(diǎn)，添加一條出邊，連到編號(hào)為(i+1)%N 的那個(gè)出度0點(diǎn),
這需要加n條邊
若 m <= n，則
加了這n條邊后，已經(jīng)沒(méi)有入度0點(diǎn)，則問(wèn)題解決，一共加了n條邊
若 m > n，則還有m-n個(gè)入度0點(diǎn)，則從這些點(diǎn)以外任取一點(diǎn)，和這些點(diǎn)都連上邊，即可，這還需加m-n條邊。
所以，max(m,n)就是第二個(gè)問(wèn)題的解
此外：當(dāng)只有一個(gè)強(qiáng)連通分支的時(shí)候，就是縮點(diǎn)后只有一個(gè)點(diǎn)，雖然入度出度為0的都有一個(gè)，但是實(shí)際上不需要增加清單的項(xiàng)了，所以答案是1，0；
程序：
/*
POJ 1236
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAXN 110
struct Node
{
int to,next;
}edge1[MAXN*100],edge2[MAXN*100];
int head1[MAXN];
int head2[MAXN];
int mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2,st[MAXN],belong[MAXN];
int num,setNum[MAXN];
struct Edge
{
int l,r;
}e[MAXN*100];
void add(int a,int b)
{
edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;
edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;
}
void DFS1(int x)//搜索原圖
{
mark1[x]=1;
for(int i=head1[x];i!=-1;i=edge1[i].next)
if(!mark1[edge1[i].to]) DFS1(edge1[i].to);
st[cnt1++]=x;
}
void DFS2(int x)
{
mark2[x]=1;
num++;
belong[x]=cnt2;
for(int i=head2[x];i!=-1;i=edge2[i].next)
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
}
int main()
{
int n;
int m;//邊數(shù)
while(scanf("%d",&n)!=EOF)
{
int w,v;
tot1=tot2=1;
for(int i=1;i<=n;i++)
{
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
}
m=0;
for(w=1;w<=n;w++)
{
while(scanf("%d",&v),v)
{
m++;
e[m].l=w;e[m].r=v;
add(w,v);
}
}
cnt1=cnt2=1;
for(int i=1;i<=n;i++)
{
if(!mark1[i])DFS1(i);
}
for(int i=cnt1-1;i>=1;i--)
{
if(!mark2[st[i]])
{
num=0;
DFS2(st[i]);
setNum[cnt2++]=num;
}
}
int out[MAXN],in[MAXN];//計(jì)算出度和入度
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
for(int i=1;i<=m;i++)
{
if(belong[e[i].l]!=belong[e[i].r])
{
out[belong[e[i].l]]++;
in[belong[e[i].r]]++;
}
}
int res1=0;//出度為0的個(gè)數(shù)
int res2=0;//入度為0的個(gè)數(shù)
for(int i=1;i<cnt2;i++)
{
if(!out[i]) res1++;
if(!in[i]) res2++;
}
//下面這個(gè)是關(guān)鍵，整張圖就一個(gè)連通分量時(shí)，輸出0，1.WR了好幾次呢
if(cnt2==2) {printf("1\n0\n");continue;}
printf("%d\n",res2);
printf("%d\n",res1>res2?res1:res2);
}
return 0;
}