一些概念连通：无向图中的任意两点都可以互相到达。强连通：有向图中的任意两点都可以互相到达。连通分量：无向图的极大连通子图。强连通分量：有向图的极大强连通子图。DFS生成树：对一张图进行深度优先遍历得到的生成树。树边：在DFS生成树上的边。前向边：由子树的根连向子树内的

蓝书的那一套理论比较生硬，且不是很深刻，故重学Tarjan。AlexWei《图论Ⅰ》相关定义割点：在无向图中，删去使得连通分量数增加的点被称为割点。割边：在无向图中，删去使得连通分量数增加的边被称为割边。点双连通图：不存在割点的无向图。边双连通图：不存在割边的无向图。点双连通分量：一

一些概念割点：无向图中，若删除点x及其连边，连通块变多，那么x为割点。点双连通：若点对x和y,删除任意非x和非y节点后，x和y仍然联通，称x和y点双连通。点双联通子图：无向图中的一个子图G，G中任意两点都是点双连通的，那么G为原图的一个点双连通子图。点双联通分量：无向图中的极大点双联通子图

是ix35老师论文的学习笔记，同时也用作连通性相关知识梳理。可能不会包含很多定义，只会挑重要的写。会包含一些例题。定义与记号\(u\rightsquigarrowv\)代表\(u\)到\(v\)的一条路径。有时也会用这个记号表示连通性。无向图点/边连通度：若\(u,v\)任意点割集大小不小

SCC学习笔记好听点的话来说，就是强连通分量。一个有向图，里面任意两个节点之间可以相互到达，我们把它称为一个强连通分量。Kosaraju首先，对于一个强连通的图，显然，他的反图也是一个强连通图。（因为原先\(A\)可以到\(B\)，\(B\)可以到\(A\)，反过来是一样的）做法是从任意一个点开始，

Part.1引入在图论问题中，我们经常去研究一些连通性问题，比如：有向图的联通性：传递闭包——Floyd算法；有向图连通性的对称性：强联通分量（SCC）——Tarjan算法缩点；无向图的联通性：并查集；无向图的关键边：桥（割边）、边双——Tarjan算法缩点；无向图的关键点：割点、点双——Tarjan建立圆方

原题链接题解唯一能解释的图片，黄色代表会执行入栈操作的点code#include<bits/stdc++.h>usingnamespacestd;intvis[500005]={0};intlow[500005]={0};stack<int>q;vector<int>ans[500005];vector<int>G[500005];intlen=0;intcnt=0;voidss(intnow,intf

省流：因为一月底回厦门玩然后又回泉州过年，直到2.17才开始做题。[APIO2018]铁人两项圆方树和后缀数组我都想开个贴单独写。考虑关于“简单路径”，在点双上都有很特殊的性质。考虑把原图的圆方树建出来，然后考虑简单路径和圆方树的关系。注意到，在同一点双的两点的简单路径的并集，

604.xsy5339怎么有人(why)605.xsy5340NOIP(noip)得到的结论是，动态凸包水太深，别碰，你把握不住。叉随机化叉了一万年，然后发现std是假的。遇到这种题来个猫树分治得了。傻逼。大粪模拟赛/tuu。606.qoj8224CaughtintheMiddle607.qoj1071The2022ICPCAsiaHan

图的连通性这个专题，不太好说，因为涉及到的东西实在是太广泛太杂了，我们这里就只讲建模，至于建模之后的处理方式可以移步至其他的知识点。强连通对于有向图，我们可以发现，如果每个点的贡献和影响与这个点可达的点有关，那么我们就可以将一个强连通分量缩点，将原图转化为一个有向无环图，然

今天在做ABC318G这道题，要用到圆方树的知识，于是就去学了圆方树。学习圆方树首先需要学习点双连通分量以及缩点，此处不多赘述。圆方树中分两种类型的点：圆点和方点。圆点指的是原来的无向图中的所有点，而方点指的是每一个点双连通分量所代表的点。相当于每一个点双连通分量就是一个

圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题那么如何建立圆

圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题那么如何建立圆

题目传送门前言本题解内容均摘自我的Tarjan学习笔记。解法Tarjan与无向图无向图与割点（割顶）在一个无向图中，不存在横叉边（因为边是双向的）。一个无向图中，可能不止存在一个割点。割点（割顶）：在一个无向图中，若删除节点\(x\)以及所有与\(x\)相关联的边之后，图将会被分

这些结论在点双大小不小于3时成立。对于点双中不同的三个点\(x,y,z\)，存在以\(x,z\)为端点，经过\(y\)的简单路径对于点双中不同的两个点\(x,y\)，存在经过\(x,y\)的简单环。对于点双中一个点\(x\)和一条边\(e\)，存在经过\(x,e\)的简单环。对于点双中两个点\(x,y(x

 点双 找到割点后一直退栈 http://ybt.ssoier.cn:8088/problem_show.php?pid=1521include<iostream>#include<algorithm>#include<cmath>#include<vector>#include<stack>usingnamespacestd;constintN=502;#defineintlonglon

0.前言最抽象的一集马上就和昨天的搞混1.几个区别啥是强连通分量？有向图的东西！现在开始就踏进无向图的大门！2.性质割点：在一个无向连通图中，如果删去某个点后，图变成不连通图，则称该点为割点。点双连通：如果一个连通图（可以是一个子图）中不含割点，则称该图是点双连通的。点双连

构建在将图变为树的方法里，圆方树与v-dcc类似。圆方树中，原来的每个点对应一个圆点，每个点双对应一个方点。故圆方树的节点数为\(n+c\)，其中\(n=|V|\)，\(c=|\text{v-dcc}|\).对于每个点双，其方点向这个点双里的每个点连边，形成一个菊花图，多个菊花图通过割点连接。割点的数量小

P3225[HNOI2012]矿场搭建一共只会删除一个点，将每个点双连通分量分三种情况讨论第一种：点双连通分量没有割点，那么为了保证一定可以逃出去，至少需要两个点第二种：点双连通分量有且只有一个割点，此处割点是绿色的点，那么对于这种点双连通分量就需要在每个只有一个割点的双连通分量

点双/边双复习笔记1.点双复习割点：图中的一个点，没有这个点的话，这个图会变成两个图点双：在一个点双内，一个点到另一个点的路径有两条及以上，并且点不会走一样的注意事项：1.割点特判：son<=1且fa=x的不是割点2.环上出发特判:son=0&&fa=x的单独一个作为点双；3.看好大于等于哦！4.low[

图论入门符号与定义基础定义：重边：端点和方向（有向图）完全相同的边称为重边。example:1212自环：自己连接自己的边称为自环。example:1111相邻相关：出边&入边从\(u\)出发的边称为\(u\)的出边；到达\(u\)的边称为\(u\)的入边。出度&入度从\(

一、定义在无向连通图\(G=(V,E)\)中，若存在一个点\(u(u\inV)\)使得删掉点\(u\)及其相连的边，会使原图不连通，就称\(u\)是原图的一个割点(cutvertex)；若存在一条边\((u,v)((u,v)\inE)\)满足删掉\((u,v)\)后会使原图不连通，就称\((u,v)\)是原图的一座桥（或

集训模拟赛的题解应该都在CWOI杂题里。主要就是题目的记录？不太想写游记。简单题不会写。7.7考试，考得依托。7.8很趣味的数据结构！感觉很有集训那味啊，就是前面讲一会简单的东西然后突然上强度。gym100739E.LifeasaMonster还是挺简单。套路地把切比雪夫距离转成曼哈顿

题目链接：http://poj.org/problem?id=2117题目大意：给定一个由\(n\)个点\(m\)解题思路：tarjan，判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案，但是同时如果\(u\)不是这个dfs树的根节点，个数还要加\(1\)。示例程序1（C++11，POJ不支持）：#include<bits/stdc++.h>

题目链接：http://poj.org/problem?id=2117题目大意：给定一个由\(n\)个点\(m\)条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。解题思路：tarjan，判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案，但是同时如果\(u\)不是这个dfs树的根节