POJ 1236 Network of Schools(强连通分量)

题目地址:POJ 1236

这个题的大意是求最少往多少点发送消息可以使任意一个点都能收到消息和最少增加多少条边可以使图为连通图。对于第一个问题,可以求入度为0的强连通块的块数,因为只有入度为0的强连通块是无法从外界接受信息的,而只要有一个入度的话,那整个连通块就都可以接收到信息。第二个问题则是求入度为0的强连通块与出度为0的强连通块的个数的最大值。

代码如下:

#include #include #include #include #include #include #include #include #include #include #include using namespace std; int head[200], cnt, index, top, ans, cntin, cntout, in[200], out[200]; int dfn[200], belong[200], instack[200], stak[200], low[200]; struct node { int u, v, next; } edge[100000]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void init() { memset(head,-1,sizeof(head)); cnt=0; memset(instack,0,sizeof(instack)); memset(dfn,0,sizeof(dfn)); top=index=ans=0; cntin=cntout=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); } void tarjan(int u) { dfn[u]=low[u]=++index; instack[u]=1; stak[++top]=u; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[v],low[u]); } else if(instack[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ans++; while(1) { int v=stak[top--]; belong[v]=ans; instack[v]=0; if(u==v) break; } } } int main() { int n, i, j, a; scanf("%d",&n); init(); for(i=1; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:POJ 2352——Stars(树状数组)
下一篇:HDU 4339 Query
相关文章

POJ 1236 Network of Schools 强

POJ 2186 Popular Cows 强连通分量

uva 11324 The Largest Clique(强

hdu 4587 2013南京邀请赛B题/ / 求

poj3177 Redundant Paths 边双连

hdu1269 迷宫城堡,有向图的强连通分

[POJ 2762]Going from u to v o

2014多校10(1001)hdu4971(强连通分

ZOJ 2588 Burning Bridges(强连通

poj2924--F - Knights of the Ro

图文推荐

POJ 1236 Network of Schools(强连通分量)
ZOJ 3640 Help Me
POJ 1236 Network of Schools(强连通分量)
CF 518C(Anya and
POJ 1236 Network of Schools(强连通分量)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-28 人气:6
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.064 (s). 10 q(s)