正文
(转载) poj1236 - Network of Schools
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
看到一篇挺好的代码，适合初学者, 转载自 博主 wangjian8006
原地址：http://blog.csdn.net/wangjian8006/article/details/7888558
题目大意：有N个学校，从每个学校都能从一个单向网络到另外一个学校，两个问题
1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
2：至少需要添加几条边，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
解题思路：
首先找连通分量，然后看连通分量的入度为0点的总数，出度为0点的总数，那么问要向多少学校发放软件，就是入度为零的个数，这样才能保证所有点能够找到
然后第二问添加多少条边可以得到使整个图达到一个强连通分量，答案是入度为0的个数和出度为0的个数中最大的那个
为什么会这样呢，经过我同学的讨论，将这个图的所有子树找出来，然后将一棵子树的叶子结点（出度为0）连到另外一棵子树的根结点上（入度为0），这样将所有的叶子结点和根节点全部消掉之后，就可以得到一整个强连通分量，看最少多少条边，这样就是看叶子结点和根节点哪个多，即出度为0和入度为0哪个多。我只能说这种策略是正确的，适用于一般图，但其实我觉得也不能够很有力的证明这个结论成立
/*
kosaraju
Memory 224K
Time 0MS
*/
#include <iostream>
using namespace std;
#define MAXV 110
#define max(a,b) (a>b?a:b) int map[MAXV][MAXV],order[MAXV],belong[MAXV],indegree[MAXV],outdegree[MAXV];
int n,num,count;
bool vis[MAXV]; void dfs(int x){
int i;
vis[x]=;
for(i=;i<=n;i++)
if(map[x][i] && !vis[i])
dfs(i);
order[++num]=x;
} void dfst(int x){
int i;
belong[x]=count; //记录结点属于哪个连通分量
vis[x]=;
for(i=;i<=n;i++)
if(!vis[i] && map[i][x])
dfst(i);
} void kosaraju(){
int i;
memset(vis,,sizeof(vis));
num=count=;
for(i=;i<=n;i++) //第一次搜索将时间戳从小到大排序
if(!vis[i]) dfs(i);
memset(vis,,sizeof(vis)); for(i=n;i>=;i--) //第二次搜索从时间戳大的开始走找连通分量
if(!vis[order[i]]){
count++; //连通分量个数
dfst(order[i]);
}
} void output(){
int i,j,inzero=,outzero=;
for(i=;i<=n;i++){
indegree[i]=outdegree[i]=;
}
for(i=;i<=n;i++) //找连通分量入度与出度
for(j=;j<=n;j++)
if(map[i][j] && belong[i]!=belong[j]){
indegree[belong[j]]++;
outdegree[belong[i]]++;
}
for(i=;i<=count;i++){ //找入度与出度为0的点
if(!indegree[i]) inzero++;
if(!outdegree[i]) outzero++;
} if(count==) //只有1个结点要特判
printf("1\n0\n");
else
printf("%d\n%d\n",inzero,max(inzero,outzero));
} int main(){
int i,a;
while(~scanf("%d",&n)){
for(i=;i<=n;i++){
while(scanf("%d",&a) && a) map[i][a]=;
}
kosaraju();
output();
}
return ;
}
另一个用tarjan算法的实现
/*
tarjan
Memory 224K
Time 0MS
*/
#include <iostream>
using namespace std;
#define MAXV 110
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b) int n,map[MAXV][MAXV],outdegree[MAXV],indegree[MAXV];
int dfn[MAXV]; //第一次访问的步数
int low[MAXV]; //子树中最早的步数
int stap[MAXV],stop; //模拟栈
bool instack[MAXV]; //是否在栈中
int count; //记录连通分量的个数
int cnt; //记录搜索步数
int belong[MAXV]; //属于哪个连通分量 void init(){
count=stop=cnt=;
memset(instack,false,sizeof(instack));
memset(map,,sizeof(map));
memset(dfn,,sizeof(dfn));
} void tarjan(int x){
int i;
dfn[x]=low[x]=++cnt;
stap[stop++]=x;
instack[x]=true;
for(i=;i<=n;i++){
if(!map[x][i]) continue;
if(!dfn[i]){
tarjan(i);
low[x]=min(low[i],low[x]);
}else if(instack[i])
low[x]=min(dfn[i],low[x]);
//与x相连,但是i已经被访问过,且还在栈中
//用子树节点更新节点第一次出现的时间
} if(low[x]==dfn[x]){
count++;
while(){
int tmp=stap[--stop];
belong[tmp]=count;
instack[tmp]=false;
if(tmp==x) break;
}
}
} void output(){
int i,j,inzero=,outzero=;
for(i=;i<=n;i++){
indegree[i]=outdegree[i]=;
}
for(i=;i<=n;i++) //找连通分量入度与出度
for(j=;j<=n;j++)
if(map[i][j] && belong[i]!=belong[j]){
indegree[belong[j]]++;
outdegree[belong[i]]++;
}
for(i=;i<=count;i++){ //找入度与出度为0的点
if(!indegree[i]) inzero++;
if(!outdegree[i]) outzero++;
} if(count==) //只有1个结点要特判
printf("1\n0\n");
else
printf("%d\n%d\n",inzero,max(inzero,outzero));
} int main(){
int i,a;
while(~scanf("%d",&n)){
init();
for(i=;i<=n;i++){
while(scanf("%d",&a) && a) map[i][a]=;
}
for(i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
output();
}
return ;
}
