图的割点tarjan---zoj_1119
- 博客分类:
- 数据结构算法
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1119
如果将连通图G中的某个点及和这个点相关的边删除后,将使原图不再连通,那么这个点就称为图G的割点或是接合点。如果一个无向图没有割点,则这样的图被称为双连通图。
算法用到了一下两个数组。
dfn:这个点在dfs序列中的位置 low:经过这个点及这个点的所有儿子能追溯到的dfn最小点的dfn值~~ 这样我们发现,如果发现low(儿子)>=dfn(父亲),那么这个父亲就是一个割点。(他的儿子向下找没法重新找到自己的父亲~) 当然这还是不够的,我们发现对于我们搜索的第一个点来说,他的dfn值是1,永远不会有点的low值比他大,所以我们要特判下,如果说他的真正的儿子(就是dfs的时候找到的儿子,也就是环不算)的个数大于1的话,他就是一个割点。 zoj_1119
#include <cstring>
#include <cstdio>
#include<algorithm>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define N 1010
bool vis[N],g[N][N];
int low[N],dfn[N],subnets[N];
int n,tmpdfn,son;
void init_tarjan()
{
memset(vis,0,sizeof(vis));
memset(subnets,0,sizeof(subnets));
memset(g,0,sizeof(g));
tmpdfn=0;
son=0;
n=0;
}
void tarjan(int u)
{
vis[u]=1;
dfn[u]=low[u]=++tmpdfn;
for(int i=1;i<=n;++i)
{
if(g[u][i])
{
if(!vis[i])
{
if(u==1)
++son;//root
tarjan(i);
low[u]=min(low[u],low[i]);
if(u!=1&&low[i]>=dfn[u])
++subnets[u];
}
else
low[u]=min(low[u],dfn[i]);
}
}
}
/*void dfs(int u)
{
//FOR(v,1,n)
for(int v=1;v<=n;++v)
if(g[u][v])
{
if(!vis[v])
{
if(u==1)
++son;
vis[v]=1;
low[v]=dfn[v]=++tmpdfn;
dfs(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
if(u!=1) subnets[u]++;
//else son++;
}
}
else low[u]=min(low[u],dfn[v]);
}
} */
void init(void)
{
low[1]=dfn[1]=1;
tmpdfn=1;
n=son=0;
memset(vis,0,sizeof(vis));
vis[1]=1;
memset(subnets,0,sizeof(subnets));
memset(g,0,sizeof(g));
}
int main(void)
{
int u,v;
int Case=1;
freopen("e:\\zoj\\zoj_1119.txt","r",stdin);
while(scanf("%d",&u)==1 && u)
{
scanf("%d",&v);
init_tarjan();
if(u>n) n=u;
if(v>n) n=v;
g[u][v]=g[v][u]=1;
while(scanf("%d",&u)==1 && u)
{
scanf("%d",&v);
if(u>n) n=u;
if(v>n) n=v;
g[u][v]=g[v][u]=1;
}
//dfs(1);
tarjan(1);
if(Case>1) puts("");
printf("Network #%d\n",Case++);
if(son>1) subnets[1]=son-1;
bool find=0;
FOR(i,1,n) if(subnets[i])
{
if(!find) find=1;
printf(" SPF node %d leaves %d subnets\n",i,subnets[i]+1);
}
if(!find) puts(" No SPF nodes");
}
return 0;
}
发表评论
-
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1642http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1708http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1316Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 864首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1277朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1665题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2479AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1185二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2130网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 866trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 914bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1072我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1658LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2839zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1364染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 744线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 776快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3073斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1283本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 940针对Bellman-Ford算法效率比较低 ...
相关推荐
Tarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms....
Blum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum...
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
Tarjan-Languer快速算法,用于在流程图中查找支配者 原料药 var pipeline = require ( 'tarjan' ) . create ( 'dominance' ) ; // Initialize pipeline // ... // ... var tarjan = require ( 'tarjan' ) . create ...
Tarjan算法求最近公共祖先,输入树和询问,按询问顺序回答
tarjan离线算法求最近公共祖先。对于有根树T的两个结点u、v,最近公共祖先LCA(T
ACM算法模板的PDF版本,方便大家打印与使用,所有模板均经过测试。...图论--割点--Tarjan模板 图论--割边--Tarjan模板 图论--边双连通V-DCC缩点 图论--双连通E-DCC缩点模板 图论--强连通
图论- 图的连通性- Tarjan 求割点与桥.rar
Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf
信息学竞赛,图论算法,Tarjan,缩点,2-SAT 寒假期间的集训讲课 PPT,主要详细讲解了 Tarjan 算法的思想及应用,同时对于 Tarjan 算法的一个扩展——2-SAT 问题进行了详细的讲解,是图论讲课非常好的课件和资料。
图论- 图的连通性- Tarjan 缩点.rar
图论- 图的连通性- Tarjan 求强连通分量.rar
图论- 图的连通性- Tarjan 求双连通分量.rar
使用 Tarjan 算法,可以有效地计算图的传递闭包。(给定一个图G , G的传递闭包 是一个包含相同顶点并包含从v 到w的边当且仅当在G中存在从v到w的路径的图。) 传递闭包在 tarjan.tc 中实现: 展开组层次结构 给定...
Tarjan割点割边,强联通分量讲解
Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共...本篇文章我们主要介绍如何使用 Tarjan 算法求解无向图的割点与桥。 我们先来简单地了解下什么是 Tarjan 算法
tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。
割点 Cut-Vertex 深度优先搜索 Depth-First-Search 堆优化的Dijkstra算法 Dijkstra(Heap-Optimised) 并查集 Disjoint-Set-Union 最大流Edmonds-Karp算法 Edmonds-Karp 欧拉函数 Euler's-Totient-Function 有向...