| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 11407 | Accepted: 4539 |
Description
Input
Output
Sample Input
5 2 4 3 0 4 5 0 0 0 1 0
Sample Output
1 2
Source
本题例子解释：
代码：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int maxn=102;
vector<int>g[maxn],gre[maxn];//存储正向图和逆图
int ord[maxn];//正向搜索，顶点的编号
bool vis[maxn];
int out[maxn];//转化为DAG以后的每个缩点的出度
int in[maxn];
int belong[maxn];//当前顶点属于哪个集合，相当于染色，当前顶点被染成了什么颜色
int ans[maxn];//每种颜色包括多少顶点,也就是强联通分量的个数
int color;//代表不同的颜色
int no;//正向搜索排序的编号
int n;//顶点数
void dfs1(int u)//从当前u顶点开始DFS
{
vis[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
dfs1(v);
}
ord[no++]=u;//为每个顶点编号
}
void dfs2(int u)
{
vis[u]=1;
belong[u]=color;//当前顶点u被染成了color
for(int i=0;i<gre[u].size();i++)
{
int v=gre[u][i];
if(!vis[v])
{
dfs2(v);
}
}
}
void kosaraju()
{
color=1,no=1;
memset(in,0,sizeof(vis));
memset(out,0,sizeof(out));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
if(!vis[i])
dfs1(i);
memset(vis,0,sizeof(vis));
for(int i=no-1;i>=1;i--)//编好号以后，从排号最大的开始搜索
{
int v=ord[i];
if(!vis[v])
{
dfs2(v);
color++;
}
}
//构造DAG
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
if(belong[i]==belong[g[i][j]])
continue;
out[belong[i]]++;
in[belong[g[i][j]]]++;
}
}
int inzero=0,outzero=0;
for(int i=1;i<color;i++)
{
if(!in[i])
inzero++;
if(!out[i])
outzero++;
}
if(color==2)
printf("1\n0\n");
else
printf("%d\n%d\n",inzero,max(inzero,outzero));
}
int main()
{
scanf("%d",&n);
int to;
for(int i=1;i<=n;i++)
{
while(scanf("%d",&to)&&to)
{
g[i].push_back(to);
gre[to].push_back(i);
}
}
kosaraju();
return 0;
}
[ACM] poj 1236 Network of Schools (有向强连通分量）
原文：http://blog.csdn.net/sr_19930829/article/details/39554371