cojs 908. 校园网
★★ 输入文件：
时间限制：1 s 内存限制：128 MB
schlnet.in 输出文件：schlnet.out 简单对比时间限制：1 s 内存限制：128 MB
USACO/schlnet(译 by Felicia Crazy)
描述
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不必也在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
PROGRAM NAME: schlnet
INPUT FORMAT (file schlnet.in)
输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
OUTPUT FORMAT(file schlnet.out)
你的程序应该在输出文件中输出两行。第一行应该包括一个正整数：子任务 A 的解。第二行应该包括子任务 B 的解。
SAMPLE INPUT (file schlnet.in)
5
2 4 3 0
4 5 0
0
0
1 0
SAMPLE OUTPUT (file schlnet.out)
- 1
- 2
- 注意：凡是涉及tarjan算法缩点的，图中缩点后只有一个点的情况必须特判。
- 非完美代码（加了特判之后，只过了七个点）：
/*一开始没注意到整张图都是一个强连通分量的情况，A任务正确，但是B任务应该输出0，而如果不特判的话，就会输出1（因为是图中的强连通分量数目（1）-可用边（0））*/
#define N 120
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<stack>
stack<int>sta;
bool visited[N]={},instack[N]={};
int dfn[N],low[N],topt=,ut=;
int father[N];
struct Edge{
int u,v,last;
}edge[N*N*],usedge[N*N*];
int uset=;
int head[N],ushead[N],n,t=,sumfl=,sumfa=;
void add_edge(int u,int v)
{
++t;
edge[t].u=u;
edge[t].v=v;
edge[t].last=head[u];
head[u]=t;
}
void input()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
int x;
while(true)
{
scanf("%d",&x);
if(x==) break;
add_edge(i,x);
}
}
for(int i=;i<=n;++i)
father[i]=i;
}
void tarjan(int k)
{
visited[k]=true;
dfn[k]=low[k]=++topt;
sta.push(k);
instack[k]=true;
for(int l=head[k];l;l=edge[l].last)
{
if(!visited[edge[l].v])
{
tarjan(edge[l].v);
low[k]=min(low[k],low[edge[l].v]);
}
else if(instack[edge[l].v])
low[k]=min(low[k],dfn[edge[l].v]);
}
if(dfn[k]==low[k])
{
sumfl++;
int pp=sta.top();
sta.pop();
instack[pp]=false;
while()
{
father[pp]=k;
if(pp==k) break;
pp=sta.top();
sta.pop();
instack[pp]=false;
}
}
}
bool flagout[N]={},flagin[N]={};
int find(int x)
{
return (father[x]==x)?father[x]:father[x]=find(father[x]);
}
void count_fa_edge()
{
for(int i=;i<=t;++i)
{
int u=edge[i].u,v=edge[i].v;
if(!flagin[v]&&!flagout[u]&&father[u]!=father[v])
{
++ut;/*统计可用边*/
flagin[v]=true;
flagout[u]=true; }
}
for(int i=;i<=t;++i)
{
int u=edge[i].u,v=edge[i].v;
if(father[u]!=father[v])
{
++uset;/*利用并查集缩点*/
usedge[uset].u=father[u];
usedge[uset].v=father[v];
usedge[uset].last=ushead[father[u]];
ushead[father[u]]=uset;
}
}
for(int i=;i<=uset;++i)
{
int u=usedge[i].u,v=usedge[i].v;
int r1=find(u),r2=find(v);
if(r1!=r2)
{
father[r2]=r1;/*重新构图*/
}
}
for(int i=;i<=n;++i)
{
find(i);
if(father[i]==i)
sumfa++;
}
}
int main()
{
freopen("schlnet.in","r",stdin);
freopen("schlnet.out","w",stdout);
input();
for(int i=;i<=n;++i)
if(!visited[i])
tarjan(i);
count_fa_edge();
if(sumfl==)
{
printf("1\n0");
}
else
printf("%d\n%d",sumfa,sumfl-ut);
fclose(stdin);fclose(stdout);
return ;
}
上述算法的反例：
这个算法是算出有多少个强连通分量，和可用边（可用边是满足每个点的入度出度都是1），然后前者减去后者。
反例：1--》2
｜ /\
\/ |
3----
这样一张图再加入1条（2--》1）边就可以满足条件了，但是如果上述算法先找到了1--》2这条边，那么1--》3和3-->2都不会找到了，那么就会判断再加入两条边，这个反例就在于
加边时的随机性，会对结果有影响。
完美代码与正确思路：
/*tarjan少写了instack[pp]=false;竟然让我调了半个多小时*/
#define N 110
using namespace std;
#include<cstdio>
#include<stack>
#include<iostream>
#include<cstring>
#include<algorithm>
int n,dfn[N],low[N],topt=;
struct Edge{
int u,v,last;
}edge[N*N*];
stack<int>sta;
int indu[N]={},outdu[N]={},ust=,ptot[N];/*indu统计所有点的入度，outdu统计所有点的出度，ptot记录了缩点后图上剩余的点*/
int father[N]={},t=,head[N];
bool visited[N]={false},instack[N]={};
void add_edge(int u,int v)
{
++t;
edge[t].u=u;/*建图*/
edge[t].v=v;
edge[t].last=head[u];
head[u]=t;
}
void input()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
int x;
while()
{
scanf("%d",&x);
if(x==) break;
add_edge(i,x);
}
}
for(int i=;i<=n;++i)
father[i]=i;
}
void tarjan(int k)
{
visited[k]=true;
dfn[k]=low[k]=++topt;
sta.push(k);
instack[k]=true;
for(int l=head[k];l;l=edge[l].last)
{
if(!visited[edge[l].v])
{
tarjan(edge[l].v);
low[k]=min(low[k],low[edge[l].v]);
}
else if(instack[edge[l].v])
low[k]=min(low[k],dfn[edge[l].v]);
}
if(dfn[k]==low[k])
{
int pp;
++ptot[];/*加入强连通分量的代表点*/
ptot[ptot[]]=k;
pp=sta.top();
sta.pop();
while()
{
father[pp]=k;/*缩点*/
instack[pp]=false;/*别忘了把设计为已出栈*/
if(pp==k) break;
pp=sta.top();
sta.pop();
}
}
}
void count_()
{
for(int i=;i<=t;++i)/*遍历所有的边，把图中剩下的边给相应的剩下的点统计入度出度*/
{
int u=edge[i].u,v=edge[i].v;
if(father[u]!=father[v])
{
outdu[father[u]]++;
indu[father[v]]++;
}
}
int in=,out=;
for(int i=;i<=ptot[];++i)
{/*遍历图中剩余的点，统计indu==0和outdu==0的点的个数*/
if(!indu[ptot[i]])
in++;
if(!outdu[ptot[i]])
out++;
}
if(ptot[]==)/*图中只有一个强连通分量的情况必须特判*/
{
printf("1\n0");
}
else printf("%d\n%d",in,max(in,out));
}
int main()
{
freopen("schlnet.in","r",stdin);
freopen("schlnet.out","w",stdout);
input();
for(int i=;i<=n;++i)
if(!visited[i])
tarjan(i);
count_();
fclose(stdin);fclose(stdout);
return ;
}