题目链接:http://poj.org/problem?id=1236
题目大意:有一些学校,学校之间可以进行收发邮件,给出学校的相互关系,问:1.至少
要向这些学校发送多少份才能使所有的学校都能获得邮件;2.若想只发送一份即可让所有学
校都能收到邮件,则至少需要需要再进行多少次学校之间的连接。
学校之间的关系可构成图,将图进行强连通缩点成块儿后可知,每个进入数为0的点需要发
送一份;若想要所有点都连接,则需要连接数目为max(入度为0点数,出度为0点数),这
个是结论,详细证明不再贴。
代码如下:
/** Memory: 604K Time: 16MS
Language: G++ Result: Accepted **/
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
vector<int>G[];
int n, Stack[], low[], dfn[], Time, Top, nblocks, belong[], inStack[];
int in[], out[];
void Init()
{
for(int i=; i<=n; i++)
{
G[i].clear();
low[i] = dfn[i] = in[i] = out[i] = inStack[i] = belong[i] = ;
}
Time = Top = nblocks = ;
}
void Tarjin(int u)
{
low[u] = dfn[u] = ++Time;
Stack[Top++] = u;
inStack[u] = ;
int v, len = G[u].size();
for(int i=; i<len; i++)
{
v = G[u][i];
if(!dfn[v])
{
Tarjin(v);
low[u] = min(low[u], low[v]);
}
else if(inStack[v])
low[u] = min(low[u], dfn[v]);
} if(low[u]==dfn[u])///强连通缩点
{
nblocks++;
do
{
v = Stack[--Top];
inStack[v] = ;
belong[v] = nblocks;
}
while(u!=v);
}
}
int main()
{
while(scanf("%d", &n)!=EOF)
{
Init();
int x;
for(int i=; i<=n; i++)
{
while(scanf("%d", &x), x)
G[i].push_back(x);
}
for(int i=; i<=n; i++)
{
if(!dfn[i])
Tarjin(i);
}
for(int i=; i<=n; i++)
{
int len = G[i].size();
for(int j=; j<len; j++)///标记缩点后的出入度
{
int u = belong[i];
int v = belong[G[i][j]];
if(u!=v)
{
out[u]++;
in[v]++;
}
}
}
int in_zero_num = ;
int out_zero_num = ;
for(int i=; i<=nblocks; i++)
{
if(!in[i])in_zero_num++;
if(!out[i])out_zero_num++;
}
if(nblocks==)
{
printf("1\n0\n");
continue;
}
printf("%d\n%d\n", in_zero_num, max(in_zero_num, out_zero_num));
}
return ;
}
/**
唐僧师徒四人一起去取经,沙僧是个细心的人,一路上照顾师徒四人的饮食起居,
这天他在整理大师兄的内裤,发现有个洞,然后就耐心的缝了起来,第二天发现
又有个洞,于是又补了起来,第三天 依旧还是有个洞,正当他拿起针线时,猴哥
过来,一脚踹飞了沙僧。尼玛,把洞缝上,尾巴搁哪儿?
**/