不积跬步，无以千里。这两天主要是复习了图的连通性相关的题+听了youwike哥哥讲课。先是复习了缩点，割点，割边，点双，边双，2-SAT，感觉比较需要注意的是割点的那个第一个节点的判断，写题的时候总是容易忘。然后又写了几道练习题。缩点#include<iostream>#include<cstring>usingna

题意如果两个线段相交（不包括端点），那么你可以从一个线段移动到另外一个线段。动态添加线段，询问能否从一个线段前往另外一个线段。思路我们不难想到利用\(scc\)来解决点对之间的关系（经典例题《炸弹》），离散化后使用权值线段树保存点对关系。具体来说，用有向边表示两个线段能相互影

这篇文章将讲述作者对Tarjan求SCC与缩点（不是割点）的理解让我们开始吧！TarjanSCC与缩点既然要求\(SCC\)那我们先要弄明白什么是SCCSCC指的是强连通分量强连通指的是若一张有向图的节点两两互相可达，则这张图是强连通的而强连通分量指的是一个极大的连通子图此处的极

定义与记号涉及常见或可能用到的概念的定义。关于更多，见参考资料。基本定义图：一张图\(G\)由若干个点和连接这些点的边构成。称点的集合为点集\(V\)，边的集合为边集\(E\)，记\(G=(V,E)\)。阶：图\(G\)的点数\(|V|\)称为阶，记作\(|G|\)。无向图：若\(e\inE\)没有

2-Sat\[\begin{align*}&\LARGE\color{Red}大意:\\&有n个数a_i,m个约束条件都需要满足\\&条件形如(i,a,j,b)\quada_i=a\\text{or}\a_j=b\\\\\\&\LARGE\color{Red}思路:\\&让a_i表示0,a_{i+n}表示1\\&转换条件表达式成:\\&a_i=a\\\te

P5782[POI2001]和平委员会大意:n个集合每个集合有两个点i,i+1一共2n个点每个集合选一个点到另一个空集S里面有m个约束条件i和j不能在一起求可行的集合S思路：2-sat对ij而言建图(i,j邻居)和(j，i的邻居),邻居就是他们所属的集合的另一个点然后判断同同一个集

P4171[JSOI2010]满汉全席-洛谷大意:n个点m个条件形如m1,h32，满足n个条件思路:2-sat让m=0，h=1，然后转换为imjh的建图，注意傻逼题目的数字可能是多位数不能直接x[1]-'0'#include<cstdio>#include<stack>#include<iostream>#include<cstring>#include<cma

[P2812校园网络【USACO]NetworkofSchools加强版大意:1.图G=(V,E)选几个点可以到达所有的点2.连多少条边可以让任意一个点出发到达其他所有点1思路:1.Tarjan跑一遍求SCC那些出度为0的点就是出发的所有点即din0的点的数量2.计算dout0的点的数量和din0的点的数量取max

\[\Large给出一个图，求出SCC后缩点得到新的图\]做法:Tarjan记录scc然后根据SCC去重新建图#include<cstdio>#include<stack>#include<algorithm>#include<iostream>#include<cstring>#include<vector>#include<queue>#defineepemplace_b

tarjan是一系列与图连通性相关的算法的统称，本文将总结常见的tarjan算法。并配合一定量的练习。无向图求割边割点割点：删掉后让整个图不联通的点。割边（桥）：删掉后让整个图不联通的边。搜索树：对图进行dfs时经过的边的集合。容易发现其构成一棵树。搜索树上的边称为树边。时间

视频链接：D362-SATP5782[POI2001]和平委员会_哔哩哔哩_bilibili   P5782[POI2001]和平委员会-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+tarjanO(n+m)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;const

图论部分\(\text{I}\).连通性部分有向图强连通分量\(\text{(SCC)}\)代码模板#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+5;intn,m,num,scc_cnt,top;boolinstk[N];intdfn[N],low[N],stk[N],blg[N];vector<int>g[N],ans_scc[N],ne

[AGC059C]GuessingPermutationforasLongasPossible（2-sat）这个东西十分智障，只需要对于所有\(a,b,c\)，如果询问顺序是\((a,b),(b,c),(a,c)\)，那么不能\(a<b<c\)或\(a>b>c\)。其它的情况（一条链）你一看发现肯定需要出现上述情况，那么这就是充要条件。你一看你直接对所

\(\texttt{0x00}\)一些概念什么是“流图”？给定有向图\(G=\{V,E\}\)，若存在\(r\inV\)，满足从\(r\)出发能到达\(V\)中的所有点，则称\(G\)为一个“流图”，记为\((G,r)\)，其中\(r\)称为流图的源点。在一个流图\(G=\{V,E\}\)上从\(r\)出发进行\(\operatorname{df

#include<bits/stdc++.h>#defineintlonglong#definedebug(x)cerr<<#x<<""<<x<<'\n';#definemultifalseusingnamespacestd;constintN=1e5+10;intt=1,n,m,h,x,y,tim,scc_count,a

2-SATsouvenir一般就是每个变量为\(0/1\)，给出很多个关于两个变量的约束然后求解啥的。下文设\(x\)表示\(1\)，\(x'\)表示\(0\)。比如\(x\oplusy=1\)，则连边\(x\toy'\)，\(x'\toy\)，\(y\tox'\)，\(y'\tox\)（单向的）。faire可以暴力DFS。时间复杂度\(\math

我们先端上来一个美味的结论。对于一张有\(n\)个点的竞赛图\(G\)，它的SCC数量等于：将\(G\)的\(n\)个点划分为两个点集\(S\)和\(T\)，且要求\(|T|>0\)，对于任意的\(u\inS\)和\(v\inT\)，\(u\)和\(v\)之间的连边方向为\(u\tov\)的方案数。考虑将图\(G\)进行

解释一下具体方案的选择首先我们先抛开蓝书，来看看如果给了我们最终的图，我们如何选择，如下于是我们所有的选择方法就是{①③，②④，①④，②③}，总之来说就是镜像对称的不能同时选择那么来看蓝书怎么搞的首先是第一种方法，其实也就是在执行普通的拓扑排序而已，但是由于队列先进先出的性

我们先不要管两个数按位与为\(1\)和两个数按位或为\(0\)的情况那么剩下的情况就是很简单的2-SAT问题就像并查集处理二元关系一样，这里最后建成的图一定是完全对称的，如下其中每个点都是一个SCC然后我们再来看剩下的两种情况，拿两个数按位与为\(1\)为例这就说明两个数必须要都是

求DAG中一条最大点权链用scc缩点完成后其实问题就回到了DAG，这样一个问题，开始dfs写多了，直接找入度为0为起点一个dfs，结果就搜爆了。正解：寻找DAG中一个拓扑排序，按照拓扑序遍历点，再遍历点的边，dp维护答案而Tarjan缩点完成后新点的倒序（ans_scc->1）就是一个拓扑序,于

一、P2812校园网络【[USACO]NetworkofSchools加强版】P2812校园网络【[USACO]NetworkofSchools加强版】1、算法简析首先，建立一张有向图——学校是节点，学校间的单向线路是有向边。\(Q_1\)：选出若干个节点，从这些节点出发可以到达其它的任意节点（即不考虑选出的节点），求这些节点

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

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

可能会有一些有一点用的trick的整理与复习。很少，很不系统。1Dinic优化给bfs和dfs加上当前弧优化。但是此时要一定注意在遍历时，\(rest=0\)退出循环需要在循环内写，而非在for中的条件写。对边权排序后分段。Dinic很多时候慢是因为边权差距太大了。于是我们不断设

主要是讲一下tarjan算法的正确性我们的连边方案是对每一对已经有了的婚姻，从女方向男方连边，然后对于交往过的关系，从男方向女方连边分析题意不难发现，如果某一对夫妻处于一个环中，那么这对婚姻关系就是不稳定的其实从环这里已经可以看出来是SCC了，我们来简单说明一下首先，如果一对夫