边双连通分量概念：若在无向图\(G\)中，存在一个极大子图\(G'\)，使得\(G'\)中没有割边，则称\(G'\)为\(G\)的一个边双连通分量，记作\(\texttt{E-DCC}\)。使用场景：将无向图转化为一棵树（即无向图上的缩点）。求解步骤：确定割边，再遍历所有点且不经过割边，那么能联通的点都是即在同一

先说一个简单问题：给定一个\(n\timesm\)的黑白网格图，每次可以将一行或者一列染成同一种色，判断是否能到达？经典做法：倒过来考虑，每次将颜色全相同或为*的一行全染成*，判断是否可以将这张图染成全*。经典网格图转二分图，如果\(s_{i,j}='W'\)则将\(i\)向\(j'\)连一条有向边，否

P3119[USACO15JAN]GrassCownoisseurG显然我们可以先跑强连通分量，由\(x\)个点缩成的新点\(u\)权值为\(v[u]=x\)。下文中的节点\(1\)均表示缩点后节点\(1\)所在的节点。我们在缩点后的DAG上跑拓扑排序，预处理出\(fa[i]\)和\(fb[i]\)，分别表示“\(1\)到\(i\)路径的点权和”，“\(i

P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解，我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”，“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图，橙色点是割点，红色框圈出的是点双，加粗的是叶子连通

如果上一场是本来都会做，但是因为题没读清楚和智障错误导致挂分后排名低，那么这一场就是纯纯脑瘫，以为题会很难，一点都没有深入思考过，结果暴力一分没挂，但是别人T1T2T3都切了，最后成了小丑

前言失而复得最开心力！！！这场AK力（可能是因为第一条）题目难度：红黄黄绿绿蓝正文A偶数-1，奇数不变B直接排个序，取前K大的就行C直接用双指针扫一遍即可D发现上下对面四个是绑定的，所以只需让上下左右四个有两对一样的即可E发现（由树剖得）一颗子树的dfn序是连续的于是就记一下d

在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\)，写篇题解纪念一下。其实，求有向图的必经点，通法就是支配树。一些定义：支配点：在确定起点\(S\)的情况下，对于一个点\(k\)，若存在\(x\)，使得删除\(x\)以及与\(x\)连接的边后，\(x\)与\(k\)，不再强连通，那么就称\(k\)为\(x

建立虚树先把关键点按\(dfn\)升序排序，单调栈维护树上一条链（\(dfn\)单增），初始为根节点\(1\)逐个考虑关键点\(x\)：设\(lca=LCA(x,st[top])\)，分类讨论：\(\hspace{0.5cm}\)①若\(lca=st[top]\)，表明\(x\)和\(st[]\)同一条链上，直接入栈；\(\hspace{0.5cm}\)②若\(lca\not=st[top]\)，则\(l

==>推倒重建版：voidtarjan(intu,intfather){ stack[++top]=v; dfn[u]=low[u]=++num; for(inti=head[u];i;i=ed[i].last) { intv=ed[i].to; if(v==father)continue; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]);

连通性问题点双连通:在无向图中，删除一个点（不是\(x\)或者\(y\)）后，点\(x\)和点\(y\)仍然能够彼此到达，那么称\(x\)和\(y\)是点双连通的。边双连通:在无向图中，删除一条边后，点\(x\)和点\(y\)仍然能够彼此到达，那么称\(x\)和\(y\)是边双连通的。性质点双连

割边在无向图中删了一条边后，图中联通块个数增加，则称该边为割边。判定对于一条\(cur\toi\)的边，若\(low_i>dfn_{cur}\)（不能取等，画图便知理由），则该边为割边。T103481&P1656板子。P1656code#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,

图论系列：前言：もしも明日がくるのならあなたと花を育てたいもしも明日がくるのならあなたと愛を語りたい走って笑って転んで相关题单：https://www.luogu.com.cn/training/641352一.割点与桥双连通分量是针对无向图来说的，有向图是强连通分量。在了解双连通分量之前需要先

割点对于一张无向图\(G=(V,E)\)，使得H是G的连通子图，且不存在\(F\)满足\(H\subsetneqF\inG\)且\(F\)为连通图，则称\(H\)是\(G\)的一个连通块/连通分量（connectedcomponent），又叫极大连通子图。由此，我们可以对割点做出如下定义：对于一个无向图，如果把一个点删除后

边双连通分量定义在一张联通的无向图中，对于任意两点\(u\)和\(v\)​，删去两点之间任意一条边，都无法使其不连通（即连通数不变），我们就说这两点是边双连通。对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量。根据【笔记/模板】割点和桥中可知，如果

前置知识：点双连通分量定义圆方树：对于一个点双内的点，拆除点之间所有相连的边，并和一个代表该点双的点连边圆点为原图中的点，方点代表一个点双圆方树有狭义和广义两种狭义圆方树不把“杠铃形”当作点双，有圆圆边广义圆方树把“杠铃形”当作点双，只有圆方边狭义圆方树是解决仙人

强连通分量细节对于多点跑tarjan来说，可能会有先访问\(u\tov\)中的\(v\)，这导致\(dfn[v]<dfn[x]\)，后面\(x\)跑tarjan时会误把\(v\)当成祖先，要加判断割点&割边删去后使图不连通的点/边找割边和强连通分量求法大差不差，这里不再赘述找割点不同于前两者，首先割点不是low[x]==dfn

传送门夏天近了，又到了恋爱的季节，小Q家门前的苹果树上结满了红红圆圆的苹果。这株苹果树是一个有着\(n\)个结点的有根树，其中结点被依次编号为\(1\)至\(n\)。\(1\)号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第\(i\)个结点上有\(a_i(a_

T1建边，发现要找偶环，但两个奇环也可以拼在一起，于是按照上面的思路模拟即可。但是挂了一个点，不知道为啥。#include<iostream>#include<vector>#include<cstring>usingnamespacestd;inlineintread(){registerintx=0,f=1;registercharc=getchar();while(c<

题目链接：https://atcoder.jp/contests/abc318/tasks/abc318_g题目大意：给出一个有\(n\)个顶点和\(m\)条边的无向连通图\(G\)，没有重边和自环。顶点的编号为\(1\simn\)，边的编号为\(1\simm\)，第\(i\)条边连接顶点\(u_i\)和\(v_i\)。给出图上三个不同的顶点\(A,B,C

LUOGU_图论ST表+DFN序LCA每次在自己的DFN序位置放入自己的父亲询问的时候l+1ST表+欧拉序LCA\(u,v\)在欧拉序中的第一个位置之间的深度最小位置就是LCA树的直径相距最远的两个点\(\max_{u,v}dis(u,v)=\max_{u,v}(dep_u+dep_v-2dep_{lca(u,v)})\)边权非负：两次BFS边权有

更新日志概念图上最小点定连通块，就是给出无向连通图上一些点，要求找出边权和最小的连通分量使这些点强连通。现在要求这个连通块内的边权之和。思路先给出结论：把节点按照dfs序排序，统计所有相邻的节点以及起始点与末尾点之间的距离，将它们求和，所求的答案即为这个和除以2。感

图论系列：前言：僕は明快さ故にアイロニー優柔不断なフォローミー後悔後悔夜の果て相关题单：戳我一.强连通分量相关定义基本摘自oiwiki，相关定义还是需要了解。(实际就是搬了个oiwiki)强连通分量主要在研究有向图可达性，针对的图类型为有向弱联通图。1.强连通定义强连通：对