POJ 1236 Network Of Schools
浏览数：26 /
时间：2015年06月09日
11：
强联通分量
第一：先求出图中有多少入度为0的点即使A的答案。
第二：先tarjan缩点，有入度为0的点N 个 出度为0的点 M个
我们只有这n m分别相连 答案为max(n,m) 就可以两两相连
CODE:
#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<string.h>
using namespace std;
const int N =111;
vector<int> G[N];
int dfn[N],low[N],belong[N],dfs_clock,scc_cnt;
stack<int> s;
void dfs(int u)
{
dfn[u]=low[u]=++dfs_clock;
s.push(u);
for (int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if (!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if (!belong[v]){
low[u]=min(low[u],dfn[v]);
}
}
if (low[u]==dfn[u])
{
scc_cnt++;
while (1)
{
int x=s.top();
s.pop();
belong[x]=scc_cnt;
if (x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
memset(belong,0,sizeof(belong));
memset(dfn,0,sizeof(dfn));
for (int i=0;i<n;i++)
if (!dfn[i]) dfs(i);
}
int main()
{
int n,i,j;
scanf("%d",&n);
for (int i=0;i<n;i++)
{
int x;
while (scanf("%d",&x)!=EOF&&x)
{
x--;
G[i].push_back(x);
}
}
find_scc(n);
if (scc_cnt==1)
{
printf("1\n0\n");
return 0;
}
int in[N], out[N];
memset(in, 0, sizeof in );
memset(out, 0, sizeof out );
for(i=0; i<n; ++i)
for(j=0; j<G[i].size(); ++j)
{
int v = G[i][j] ;
if(belong[i] != belong[v])
{
out [ belong[i] ]++;
in [belong[v] ]++;
}
}
int in_tot = 0, out_tot = 0;
for(i=1; i<=scc_cnt; ++i)
{
if(!in[i]) in_tot++;
if(!out[i]) out_tot++;
}
printf("%d\n%d\n", in_tot,max(in_tot,out_tot));
return 0;
}
SCC 的模板
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
