缩点专题

【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖

传送门：【HDU】3861 The King’s Problem 题目分析：首先强连通缩点，因为形成一个环的王国肯定在一条路径中，这样才能保证拆的少。然后缩点后就是DAG图了，由于题目要求的是最小路径覆盖，那么二分匹配即可。代码如下： #include <cstdio>#include <cstring>#include <algorithm>#includ

缩点专题总结

~~~~~ 总题单链接 ~~~~~ 缩点，就是把一个强连通分量缩成一个点。 ~~~~~ 若我们不需要每个点的信息，只需要每个强连通分量的信息就可以用缩点。 ~~~~~ 缩点后的图是一颗树或者森林，有着非常好的性质。

【tarjan缩点+小拓展】【POJ-2186】

用刚搞到的模板，去过了一道题差不多是个模板题有一群奶牛，奶牛A可以关注B，关注具有传递性，给出奶牛之间的关注关系，问有几只奶牛得到了所有其他奶牛的关注？互相关注的可以看成一个点，所以直接tarjan算法 + 缩点新图中，出度为0的点只能有一个，因为如果有两个，这两个新点（原连通分量）就一定是互相没有关注联系的然后答案就是这个出度为0 的新点（原连通分量）中包含的原来点的个

【hh大神的】Tarjan + 缩点模板

此模板来自 notonlysuccess 原文链接： http://www.notonlysuccess.com/index.php/tarjan/ 大神就是吊啊。不多说了，想学tarjan ，资料网上是有一堆的怎么说。。我现在理解的还不算太透彻，但用模板总行吧这里只存一下模板使用时注意清空和存图！（基于个人习惯，稍微有些小改动） #define

【Redundant Paths】【无向图】【双连通分量】【缩点】

Redundant Paths Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status In order to get from one of the F(1≤F≤5,000) grazing fields (which a

HDU1827 Summer Holiday（强连通+缩点+最小传递费用）

题意：给出人物关系图，要把一个通知告诉所有人，告诉每一个人有一个费用，现在想知道最小通知的人与费用。思路：利用Tarjan算法，对原图进行缩点，然后找出入度为0 的点，那么这个人是必须要通知的，由于经过缩点，所以，如果这个点是缩点来的，那就枚举下这个点里的任一个点，找到最小的费用点。 #include<cstdio>#include<iostream>#include<algorith

HDU2767Proving Equivalences（强连通+缩点+ 至少加几条边让整个图变成强连通））

题意：至少加几条边让整个图变成强连通。思路：对于N个点的图，我们知道至少需要N条边才能使这个图强连通，现在我们先对题目的图计算一下强连通，对于已经在一个强连通的点，把他们看做为一个点，然后对新形成的图，计算出度，入度为0的最大值，因为，加一边，可以使入度，出度加一。 #include<cstdio>#include<iostream>#include<algorithm>#incl

poj 3352 Road Construction(边连通+tarjan+缩点)

http://poj.org/problem?id=3352 题意：简化一下原题题意，意思就是给定一个连通图，问至少要加入几条边使得整个图变成一个边连通图，即图中任意两点都有两条以上的路径（不一定直接相连）。思路：tarjan算法，设置一个low数组，在建立深搜树的过程中，我们会得到每个节点的low值，对于low值相等的节点在同一个双连通分量中。由于在同一个边连通分量中的点的“地

poj 2186 Popular Cows（tarjan + 强连通分量 + 缩点）

http://poj.org/problem?id=2186 题意：有n头牛，m个膜拜关系，膜拜关系是不可逆的而且是单向传递的，比如A膜拜B，B膜拜C,那么A也膜拜C，但B不一定膜拜A。最后问有多少头牛满足条件：除了它自己，其他所有的牛都膜拜它。思路：问题可以抽象为：给定一个有向图，n个顶点，m条有向边，有多少个顶点满足：其他所有的点都能到达该点。首先假如图G是一个有向树

训练赛 Grouping(强连通分量缩点 + DAG求最长路)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=158#problem/F 大致题意：给出n个人和m种关系(ti,si)，表示ti的年龄不小于si。问最小能被划分为几个集合，每个集合都要满足里面的人都无法比较。思路：对于一条路上的点，它们必定不能被划分到同一个集合中，因此原题变为求一条最长路。而题目中有可能出现

codeforces #427C Checkposts（强连通缩点）

题目地址：http://codeforces.com/problemset/problem/427/C 强连通缩点模板题。。想要设置站点最少，那就每个强连通块只放一个就可以了，要使总花费数最少，就每个强连通块取花费最少的区域。计算方法数的时候，只需要计算每个块最少的区域可选的个数乘起来就可以了。代码如下： #include <iostream>#include <cstdio>#i

T103440 【模板】缩点

题目地址易错点：出栈时应将inStck[y]置空. #include<cstdio>#include<iostream>using namespace std;const int MAXN=1e5,MAXM=1e6;struct Edge{int from,to,nxt;}e[MAXM];int head[MAXN],edgeCnt=1;void addEdge

POJ-2186 Popular Cows 强连通 + 缩点

http://poj.org/problem?id=2186 我们求强连通分量时，给每个顶点做一个标记，标记该顶点属于哪个强联通分量，然后属于同一个强连通分量的点就可以看作同一个点了。这就是所谓的“缩点” 此题用了个定理：有向无环图（DAG）中，从任意一个点出发，必定可以到达某一个出度为0的点。这个不用证明，直观想一下就行了。因为无环，所以从一个点出发，必

poj 3117poj 3352 （边双连通分量+缩点 Tarjan算法）

分析：在同一个边双连通分量中，任意两点都有至少两条独立路可达，所以同一个边双连通分量里的所有点可以看做同一个点。缩点后，新图是一棵树，树的边就是原无向图的桥。现在问题转化为：在树中至少添加多少条边能使图变为双连通图。结论：添加边数=（树中度为1的节点数+1）/2 具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩

hdu 5458 Stability(树链剖分+强连通缩点+线段树)

题目链接：hdu 5458 Stability 解题思路先将操作处理一遍，获得最终图，然后对图进行双联通缩点，剩下的肯定是一棵树，然后将操作逆着做一遍，遇到删边等于是加一条边，加的这条边u，v等于是将两节点路径上的点联通起来变成一个新的双联通分量，在同一个双联通分量中，明显ans=0。所以我们用线段树维护树的每条边权，一开始全为1，每次添加一条边，就将这条路径上的边权值置为0。代码 #

zoj3781 Paint the Grid Reloaded --- 缩点 bfs

╮(╯▽╰)╭水题相连的相同色块缩成点，和相邻的不同色块建边。以每一个点为起点bfs，求最小答案。题意：给一个n*m的X O构成的格子（其实给的是n*n，但处理时都当做n*m，真是奇怪啊），对一个点操作可以使与它相连通的所有一样颜色的格子翻转颜色（X—>O或O—>X），问给定的矩阵最少操作多少次可以全部变成一样的颜色。思路：每次操作都将本身所在的连通块与和自己相邻

Codeforces 1463 E. Plan of Lectures（缩点，拓扑排序）

题意：要求你构造一个 n n n的排列，要满足： a [ i ] a[i] a[i]出现在 i i i之前，如果 a [ i ] = 0 a[i]=0 a[i]=0代表这个数没有限制。仅对条件一保证一定有解。有 k k k个特殊对 ( i , j ) (i,j) (i,j)，要求满足 i i i在排列中一定在 j j j的左边。询问是否存在这样的排列。思路：这场的 E E E题简单

tarjan求强连通分量+缩点+割点以及一些证明

“tarjan陪伴强联通分量生成树完成后思路才闪光欧拉跑过的七桥古塘让你心驰神往”----《膜你抄》自从听完这首歌，我就对tarjan开始心驰神往了，不过由于之前水平不足，一直没有时间学习。这两天好不容易学会了，写篇博客，也算记录一下。一、tarjan求强连通分量 1、什么是强连通分量？引用来自度娘的一句话： “有向图强连通分量

HDU1827 Summer Holiday 解题报告【tarjan/强连通分量+缩点】

Problem Description To see a World in a Grain of Sand And a Heaven in a Wild Flower, Hold Infinity in the palm of your hand And Eternity in an hour. —— William Blake 听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴

#tarjan，树形dp#洛谷 3387 【模板】缩点

题目给定一个 n n n个点 m m m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。分析那么这道题首先要把环缩点，然后在有向无环图跑一遍dp，但是tarjan还是很难理解代码 #include <cstdio>#include <cctype>#inc

[tarjan缩点][拓扑排序]Trick Or Treat On The Farm

题目描述每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N个牛棚里转悠，来采集糖果.她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果. 农场不大，所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛棚”.牛棚i的后继牛棚是next_i 他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段，来节约他

[拓扑排序][tarjan缩点]自行车比赛

题目描述自行车赛在一个很大的地方举行，有N个镇，用1到N编号，镇与镇之间有M条单行道相连，起点设在镇1，终点设在镇2。问从起点到终点一共有多少种不同的路线。两条路线只要不使用完全相同的道路就被认为是不同的。 Input 第一行两个整数：N和M(1<=N<=10000,1<=M<=100000)，表示镇的数量和道路的数量。接下来M行，每行包含两个不同的整数A和B，表示有一条从镇A到镇

【ybt】【图论强连通课过例1】有向图缩点

有向图缩点题目链接：有向图缩点题目描述解题思路强连通分量模板，用 T a r j a n Tarjan Tarjan 算法。 code #include<iostream>#include<cstdio>#include<queue>using namespace std;queue<int> q;int n,m;int ans;int tm,tt;int

Tarjan-vDCC，点双连通分量，点双连通分量缩点

前言双连通分量是无向图中的一个概念，它是指无向图中的一个极大子图，根据限制条件可以分为边双连通分量和点双连通分量，欲了解双连通分量需先了解Tarjan算法，以及割点割边的概念及求解。本篇博客介绍点双连通分量的相关内容。前置知识学习点双连通分量前，你需要先了解：关于Tarjan：SCC-Tarjan算法，强连通分量算法，从dfs到Tarjan详解-CSDN博客关于缩点：S

【算法每日一练]-图论（保姆级教程篇12 tarjan篇）#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

目录 POJ3352：道路建设思路： POJ2553：图的底部思路： POJ1236校园网络思路：缩点：思路： POJ3352：道路建设由于道路要维修，维修时候来回都不能走，现要在各个景点间建设新道路以便维修时候也能保证任何

poj-3352-Road Construction-缩点

做法：把所有的边双联通分量缩成一个点。之后建树，然后求出这个树中度为1的点。 #include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>#include<queue>#include<stack>#include<map>#include<vector>#include<stdlib