强连通分量SSC(缩点)有向图缩点（把一个强连通分量看成一个点），用于优化。树枝边：DFS时经过的边，即DFS搜索树上的边反祖边：也叫回边或后向边，与DFS方向相反，从某个结点指向其某个祖先的边横叉边：从某个结点指向搜索树中另一子树中的某结点的边，它主要是在搜索的时候遇到了

得用kunkka号看。题解A.网瘾少年很好很好的贪心题。弱化版是[CSP-J2023]公路，这题没有油箱限制。首先判掉无解：存在\(d_i>T\)。用单调栈求\(nxt_i\)表示\(i\)之后第一个油价比\(i\)低的位置，没有为\(n+1\)（终点）。因为\(nxt_i\)的油价比\(i\)低，所以你肯定

题意给出一个\(n\)个点，\(m\)条边的无向图，对其进行\(k\)次操作，每次操作会删除一个当前无向图中存在的点及其相邻的边，求原图和每次操作之后的图的连通块个数sol由于需要计算连通块个数，可以自然的想到使用并查集解决。然而，删除某个点后，我们无法通过并查集快速地得知其与其他

【洛谷】P4819[中山市选]杀人游戏的题解题目传送门题解Tarjan我可爱的Tarjan嘻嘻qaq枚举每一个点，然后枚举每条出边，如果相连的两个点在同一个强连通分量中，或者xx

A-MoneyinHand（记忆化搜索）原题链接题解B-GoodGraph（并查集）原题链接题解C-IceSkating（dfs求连通块）原题链接题解D-TheLakes（dfs求连通块，连通块内累加，多组数据注意初始化）原题链接题解E-LearningLanguages(建图，dfs统计连通块个数，答案为个数-1）原题链接题

2A题意：\(1\simn\)排在数轴上，定义\(con_{i,j}=[i,j\text{直接或间接连通}]\)，当前局面的代价为\(\sum_{i<j}con_{i,j}\timesa_{j-i}\)。初始连满\(\frac{n(n-1)}{2}\)条边，求恰好删去\(0,1,\cdots,\frac{n(n-1)}{2}\)条边后的最小代价。\(n\le100,a_

十三联测#7B已知有一棵树，有\(n-1\)次操作，每次操作之前没有操作过的点\(x\)：新建节点\(x+n\)，并扫描原树上与\(x\)连接的点\(j\)，若存在\((j+n,x)\)的边就删掉，换成\((j+n,x+n)\)。否则，加入\((x+n,j)\)这条边。每次操作完询问生成树的个数。\(n\le5000\)。非常难

简介：使用该工具可以快速的测试端口网络连通情况1.下载Tcping.exe应用程序网站：tcping.exe-pingoveratcpconnection(elifulkerson.com)2.全局适用将下载好的Tcping.exe应用程序，移动到C:\Windows\System32文件夹下3.CMD窗口测试网络口段连通情况win+R：打开运行对话

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

Description给一个长度为\(n\)的数组\(a\)，\(a\)中的元素两两不同。对于每个数对\((i,j)(i<j)\)，若\(a_i<a_j\)，则让\(i\)向\(j\)连一条边。求图中连通块个数。支持\(q\)次修改数组某个位置的值，每次修改后输出图中连通块个数。\(n,q\le5\times10^5,1\lea_i\le10^

\(\text{Tarjan}\)1.引入概念1.强连通分量1.定义在有向图\(G\)中，强连通分量就是满足以下条件的\(G\)的子图：从任意一点出发，都有到达另一个点的路径。不存在一个或者几个点，使得这个子图加入这些点后，这个子图还满足上一个性质。为什么要限定”在有向图中“而不是”在任

图的连通性强连通分量割点缩点例题一边双连通分量点双连通分量2-SAT例题二例题三欧拉回路例题四

https://mna.wang/contest/1412/problem/3很好很好的计数题。给定一个\(n\timesm\)的网格图，其中.表示空地，#表示障碍物。你需要选出恰好两个不同的障碍物，将它们变成空地，使得操作完成后，节点\((1,1)\)和\((n,m)\)恰好通过空地四联通，保证初始时\((1,1)\)和\((n,

快乐的流畅：个人主页个人专栏：《C游记》《进击的C++》《Linux迷航》远方有一堆篝火，在为久候之人燃烧！文章目录引言一、图的概念二、图的存储结构2.1邻接矩阵2.1.1成员变量与默认成员函数2.1.2GetIndex2.1.3AddEdge2.1.4Print2.2邻接表2.2.1结点2.

[清华集训2012]串珠子题意给定\(n\)个点和\(n\timesn\)的矩阵\(c\)。有\(c_{i,j}\)种方案把点\(i\)和点\(j\)连接起来。求有多少种方案使得整张图连通。思路注意到\(1\len\le16\)，考虑状压。定义\(g_i\)为集合\(i\)的连边方案数，有\[g_i=\prod_{u,v\i

水一篇题解。也是一道并查集的好题，涉及另一个并查集的基本应用，并查集维护连通块（我跟并查集过不去了？？？）大致题意：给你一棵树，对于每次询问求一个点所在连通块中到达该点的最小路径权值大于给定值的点个数。既然都连通块了，那我们在维护连通块的时候直接不把权值大于K的边加进去，用并查

T2树上异或题面分析树形DP题考虑一颗子树内部的某种割边方式，假设其被分为\(n\)个连通块，每个连通块的权值分别为\(a_1,a_2,\dots,a_n\)，那么该子树在这种割边方式下对答案的贡献就为\(\prod_{i=1}^{n}a_i\)。因此就可以从叶子向根不断合并，求出每种割边状态的值，时

前言DFS树无向图DFS树定义：DFS树是在图或树结构上进行深度优先搜索时形成的树。在DFS过程中，从一个顶点开始，尽可能深地搜索图的分支，直到达到一个没有未访问邻居的顶点，然后回溯到上一个顶点继续搜索。从点\(r\)开始搜索，每次进入一个点\(i\)对应的边\((fa_i,i)\)为树

T1AmusementPark题意：通信题。给定一张\(n\)个点\(m\)条边的无向连通图。Alice会得到一个\([0,2^{60})\)中的数\(x\)，并且她需要给这张图上每一个结点标一个数字\(a_i=0/1\)。然后Bob也会拿到这张图（编号和Alice的一样），但是他不知道\(x\)，也不知道所有点上的数字

水影若深蓝：挺好的一道并查集构造题。观察不难发现“距离为\(2\)”这个条件我们可以通过黑白染色实现，我们把他们的中转点染成与他们相反的颜色，把这两个距离为\(2\)的点染成相同颜色。这个染色问题就很并查集。于是我们用并查集维护相同的种类。显然，当图上只有一个连通块的

题意给定一个由黑白组成的网格。保证黑子四联通。规定一次操作为使用最初的网格图替换当前网格图的所有黑色格子。操作\(k\)次。问最终有多少个黑色连通块，对\(10^9+7\)取模。\(k\le10^{18}\)。Sol先不难注意到这个东西只和原网格图是否左右联通和上下联通有关

板子连线过程中注意事项：第一，不能距离边缘过近第二，走线不能过长，保证焊盘焊盘间距离短（拒绝太多折线连接）第三，在布线途中旋转器件，确保连接第四，确保GND线可以互相连通如果未连接地线，通过铺铜连接地线时注意事项：1.这样连接是锐角，不能哦  (同一层线不能锐角)   2.铺

[ARC101E]RibbonsonTree题解其实算一道好题了。首先考虑不相关的simple的dp。平凡的想法是设\(dp_{i,j}\)表示\(i\)子树内有\(j\)个点还需要向上转移的方案数。转移式大概是个\(dp_{x,i+j}=dp_{y,i+j-1}+(dp_{p,i-1}+dp_{q,j-1})\)之类的东西。这样的dp是\(O(

RoadoftheKing题解形成强连通图的必要条件是点\(1\)能在环中，于是考虑\(1\)号点形成的强连通分量\(x\)。这类图论计数题目往往考虑dp，于是我们设\(dp_{i,j,k}\)表示走了\(i\)步，经过了\(j\)个点，\(1\)号点形成的强连通分量\(x\)的大小为\(k\)时的方案数。转移

1.给定两个正整数n,m，米小游想要求出n-m中的所有整数的哪个数字中4的数量加上6的数量最多。如果有多个这样的数字，请输出最大的。例如某一个数字是44624，则它有3个4，1个6，所以4和6的数量之和为4。打卡题intmain(intargc,char*argv[]){intn,m;cin>>n>>m;i