#include<bits/stdc++.h>
using namespace std;
const int maxn=100004,maxm=100004;
int n,m=0,dfn[maxn],low[maxn],head[maxn],vis[maxn],cnt=0,deep=0,col[maxn],sum=0,num[maxn],out[maxn],ans=0,in[maxn];
stack<int>s;
struct node{
    int to,next;
}e[maxm];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int u){
    vis[u]=1;
    dfn[u]=low[u]=++deep;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }   
    if(dfn[u]==low[u]){
        col[u]=++sum;
        vis[u]=0;
        while(1){
            int x=s.top();
            s.pop();
            col[x]=sum;
            num[col[x]]++;
            vis[x]=0;
            if(u==x) break;
        }
    }
}
void shrink_point(){
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=e[j].next){
            int v=e[j].to;
            if(col[i]!=col[v]) {out[col[v]]++;in[col[i]]++;}
        }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int j;
        while(cin>>j){
            if(j==0) break;
            m++;add(i,j);
        }
    }
    for(int i=1;i<=n;i++)
     if(!dfn[i]) tarjan(i);
    shrink_point();
    int ans1=0;
    for(int i=1;i<=sum;i++){
     if(!out[i]) ans++;
     if(!in[i]) ans1++;
    }
    if(sum==1) cout<<"1"<<endl<<"0";
    else cout<<ans<<endl<<max(ans,ans1);
}

邻接矩阵
tarjan算法
题解：使用tarjan求强连通分量，求出的强连通分量可以看成一个点(叫做缩点)，缩点后的图中入度为0的点的个数为a，出度为0的点的个数为b。
第一问的答案就是a，第二问的答案就是max(a,b);

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define M 150
using namespace std;
int n,m,deep[M],low[M],v[M],tot,ans,inz[M],ans1,ans2,z[100100],belong[M],a[M][M],in[M],out[M],top;
void tarjan(int x)
{
    z[++top]=x;
    v[x]=1;
    inz[x]=1;
    deep[x]=++tot;
    low[x]=++tot;
    for(int i=1;i<=n;i++)
    {
        if(a[x][i]==1)
        {
            if(v[i]==0)
            {
                tarjan(i);
                low[x]=min(low[x],low[i]);
            }
            else
            {
                if(inz[i]==1)
                {
                    low[x]=min(low[x],deep[i]);
                }
            }
        }
    }
    if(deep[x]==low[x])
    {
        ans++;
        int t;
        do
        {
            t=z[top--];
            inz[t]=0;
            belong[t]=ans;
        }while(t!=x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int to;
        while(scanf("%d",&to)&&to)
        {
            a[i][to]=1;
        }
    }
    for(int i=0;i<=n;i++)
    {
        a[i][i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(deep[i]==0)
        {
            tarjan(i);
        }
    }
    if(ans==1)
    {
        printf("1\n0");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]&&i!=j)
            {
                if(belong[i]!=belong[j])
                {
                    out[belong[i]]++;
                    in[belong[j]]++;
                }
            }
        }
    }
    for(int i=1;i<=ans;i++)
    {
        if(in[i]==0)ans1++;
        if(out[i]==0)ans2++;    
    }
    ans2=max(ans1,ans2);
    printf("%d\n%d",ans1,ans2);
    return 0;
}

Kosaraju 比 Tarjan 好写多了 (挑战写法）

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
int n, res1, res2, cmp[maxn], in[maxn], out[maxn];
bool vis[maxn];
vector<int> G[maxn], rG[maxn], vs;

void add_edge(int u, int v) {
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int u) {
    vis[u] = true;
    for (int v : G[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    vs.push_back(u);
}

void rdfs(int u, int k) {
    vis[u] = true;
    cmp[u] = k;
    for (int v : rG[u]) {
        if (!vis[v]) {
            rdfs(v, k);
        }
    }
}

int scc() {
    memset(vis, false, sizeof(vis));
    vs.clear();
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    memset(vis, false, sizeof(vis));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
        if (!vis[vs[i]]) {
            rdfs(vs[i], ++k);
        }
    }
    return k;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int u = 1, v; u <= n; u++) {
        while (cin >> v && v != 0) {
            add_edge(u, v);
        }
    }
    int k = scc();
    for (int u = 1; u <= n; u++) {
        for (int v : G[u]) {
            if (cmp[u] != cmp[v]) {
                out[cmp[u]]++;
                in[cmp[v]]++;
            }
        }
    }
    for (int i = 1; i <= k; i++) {
        if (!out[i]) {
            res1++;
        }
        if (!in[i]) {
            res2++;
        }
    }
    if (k == 1) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }
    cout << res2 << endl << max(res1, res2) << endl;
    return 0;
}

#6点错了的，可能是没有特判“只有一个强联通分量”的情况

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6069301.html

此题很沙茶。

通过率巨高……

USACO 5.3 schlnet

没打算做。IOI。。囧rz..

沙茶题……

题解地址：http://xujieqi.blog.hexun.com/35535204_d.html

感谢上天给我这样的一个机会：

我第八个！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

First Blood!!!

终于拿了一血...把I打成0害我多交了1次...

Kosaraju算法收缩强连通分量...

地幔。。。

第5个

第三

第二

Network of Schools
cpp
#include <iostream>
#include <stack>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
/*优化读入
*@ param l 要读入的int
*/
char ch_buffer;
bool signum;
inline void readInt(int&l) {
l=0;
do ch_buffer=getchar();
while((ch_buffer<'0'||ch_buffer>'9')&&ch_buffer!='0'&&ch_buffer!='-');
if(ch_buffer=='-')ch_buffer=getchar(),signum=true;
while(ch_buffer<='9'&&ch_buffer>='0')l=(l<<3)+(l<<1)+ch_buffer-'0',ch_buffer=getchar();
if(signum)l=-l,signum=false;
}
#define M 110/*题目中可能的最大点数*/
stack<int> st;/*tarjan算法中的栈*/
int DFN[M];/*深度优先搜索访问次序*/
int Low[M];/*能追溯到的最早的次序*/
int ComponentNumber=0;/*有向图强连通分量个数*/
int Index=0;/*索引号*/
vector<int> Edge[M];/*邻接表表示*/
vector<int> Component[M];/*获得强连通分量结果*/
int InComponent[M];/*记录每个点在第几号强连通分量里*/
int ComponentDegree[M];/*记录每个强连通分量的度*/
int inDegree[M];/*入度*/
int outDegree[M];/*出度*/
/*所给点的数量*/
int n;
/*无向图插入
*@ param u 第一个顶点编号
*@ param v 第二个顶点编号
*/
inline void insertMulty(int u,int v) {
Edge[u].push_back(v),Edge[v].push_back(u);
}
/*有向图插入
*@ param u 顶点编号
*@ param v 连通顶点的编号
*/
inline void insert(int u,int v) {
Edge[u].push_back(v);
}
/*初始化
*@ param num_of_n 顶点的数量
*/
inline void init(int num_of_n) {
memset(DFN,0,sizeof(DFN));
memset(Low,0,sizeof(Low));
memset(inDegree,0,sizeof(inDegree));
memset(outDegree,0,sizeof(outDegree));
while(!st.empty()) st.pop();
ComponentNumber=Index=0;
n=num_of_n;
}
/*tajan+缩点*/
void tarjan(int u) {
DFN[u]=Low[u]=++Index;
/*入栈*/
st.push(u);
int v;
/*for each (u, v) in E*/
for (int e=0; e<Edge[u].size(); e++) {
v=Edge[u][e];
if (!DFN[v]) {
tarjan(v);
Low[u]=min(Low[u],Low[v]);
/*!InComponent[v]=>如果不在栈中,*/
/*这里用这种写法,既可以缩点还能节约一个boolean数组*/
} else if (!InComponent[v]) Low[u]=min(Low[u],Low[v]);
}
if (DFN[u]==Low[u]) {
ComponentNumber++;
do {
v=st.top(),st.pop();
/*记录强连通分量*/
Component[ComponentNumber].push_back(v);
/*缩点=>degree*/
InComponent[v]=ComponentNumber;
} while (v!=u);/*until v==u*/
}
}
/*缩点*/
inline void degree() {
/*遍历*/
for(int i=0; i<n; i++) {
for(int j=0; j<Edge[i].size(); j++) {
int k = Edge[i][j];
/*这里的InComponent指的是点对应的强连通分量的编号*/
/*等价于网上许多教程中的belong数组*/
if(InComponent[i] != InComponent[k]) {
/*统计入度*/
inDegree[InComponent[k]]++;
/*统计出度*/
outDegree[InComponent[i]]++;
}
}
}
}
int x;
int main(int argc, char const *argv[]) {
/* code */
//freopen("in.in","r",stdin);
readInt(n);
init(n);
for(int i=0; i<n; i++) {
/*在c++中,while只根据最后一个","后的变量来判定条件是否成立*/
while(readInt(x),x)
/*所有编号都-1,节约空间*/
/*如编号为1,存入为0*/
x--, insert(i,x);
}
/*上面编号已减1,故从0开始遍历*/
for(int i=0; i<n; i++)
if(!DFN[i]) tarjan(i);
/*特殊情况节约时间,避免再往下运行*/
if(ComponentNumber==1)cout<<"1\n0\n",exit(0);
/*缩点*/
degree();
/*统计入度为0的点*/
int in_tot=0,out_tot=0;
for(int i=1; i<=ComponentNumber; i++) {
if(!inDegree[i]) in_tot++;
if(!outDegree[i]) out_tot++;
}
cout<<in_tot<<"\n"<<max(in_tot,out_tot);
return 0;
}


额，感觉和一道例题一样···
#include <cstdlib>
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

const int maxn=10000;
int pre[maxn],lowlink[maxn],sccno[maxn],dfsclock,scccnt;
vector<int>G[maxn];
stack<int>S;
int n;
void dfs(int u){
pre[u]=lowlink[u]=++dfsclock;
S.push(u);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);

}else if(!sccno[v])lowlink[u]=min(lowlink[u],pre[v]);

}
if(lowlink[u]==pre[u]){
scccnt++;
for(;;){
int x=S.top();
S.pop();
sccno[x]=scccnt;
if(x==u)break;

}
}
}
void find(int n){
dfsclock=scccnt=0;
memset(sccno,0,sizeof(sccno));
memset(pre,0,sizeof(pre));
for(int i=0;i<n;i++)
{
if(!pre[i])dfs(i);
}

}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a;
while(cin>>a&&a!=0)
{
G[i].push_back(a-1);
}

}
find(n);

//cout<<scccnt<<endl;
int in0[maxn],out0[maxn];
for(int i=1;i<=scccnt;i++)in0[i]=out0[i]=1;
for(int u=0;u<n;u++)
for(int u=0;u<n;u++)
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(sccno[u]!=sccno[v])in0[sccno[v]]=out0[sccno[u]]=0;

}
int a=0,b=0;
int ans1,ans2;
for(int i=1;i<=scccnt;i++)
{
if(in0[i])a++;
if(out0[i])b++;

}
ans2=max(a,b);
if(scccnt==1){a=1,ans2=0;}
cout<<a<<endl;
cout<<ans2<<endl;
system("PAUSE");
return 0;
}

var
a : array[1..100,0..100] of longint;
n,i,j,ti,top,cnt,ans1,ans2,k : longint;
sta,dfn,scc,low,inp,outp : array[0..107] of longint;

function min(a,b : longint) : longint;
begin
if a<b then exit(a) else exit(b);
end;

procedure dfs(k : longint);
var i,v,x : longint;
begin
inc(ti); dfn[k] := ti; low[k] := ti;
inc(top); sta[top] := k;
for i := 1 to a[k,0] do begin
v := a[k,i];
if dfn[v]=0 then begin
dfs(v);
low[k] := min(low[k],low[v]);
end else
if scc[v]=0 then low[k] := min(low[k],dfn[v]);
end;
if low[k]=dfn[k] then begin
inc(cnt);
repeat
x := sta[top]; dec(top);
scc[x] := cnt;
if x=k then break;
until false;
end;
end;

begin
readln(n);
for i := 1 to n do begin
read(j);
while j<>0 do begin inc(a[i,0]); a[i,a[i,0]] := j; read(j); end;
readln;
end;
for i := 1 to n do
if dfn[i]=0 then dfs(i);
for i := 1 to n do
for j := 1 to a[i,0] do begin
k := a[i,j];
if scc[k]<>scc[i] then begin
inc(inp[scc[k]]); inc(outp[scc[i]]);
end;
end;
for i := 1 to cnt do
if inp[i]=0 then inc(ans1) else
if outp[i]=0 then inc(ans2);
if ans1>ans2 then ans2 := ans1;
if cnt=1 then ans2 := 0;
writeln(ans1); writeln(ans2);
end.

强连通分量果然比双连通好打多了嗯哼~

如果只有一个强连通分量，那么任务a=1，任务b=0；