搜索结果
查询Tags标签： dfn，共有 46条记录-
CF375E Red and Black Tree
题目传送门 Solution 非常神奇的一道题。 我们不考虑交换操作，相反，我们去考虑把多少个 \(0\) 的位置变为 \(1\)，同时我们记录选了多少个黑点，如果跟原来黑点数量相同即是合法。 此时我们可以发现一个神奇的性质对于 \(u\) 的儿子 \(v\)，如果覆盖 \(u\) 的节点不覆盖…
2022/8/31 23:26:17 人评论 次浏览 -
求一个图的最打的半联通子集=求一个图的最长链方案和个数
拓扑图最长路 等于 背包问题求方案数 因为要求点不同 存在多条边同一情况 需要边判重(set) 拓扑求方案数 #include <iostream> #include <cstring> #include <algorithm> #include <unordered_set>using namespace std; typedef long long LL; c…
2022/8/30 23:53:03 人评论 次浏览 -
2022.7.31学习笔记
主要内容： 1.最小瓶颈路2.kruskal 重构树3.差分约束系统4.强连通分量5.DFS树6.kosaraju算法求SCC7.tarjan算法求SCC8.SAT问题 最小瓶颈路 模板：#include<bits/stdc++.h> #define re return #define lowbit(x) (x&(-x)) #define dec(i,l,r) for(int i=l;i>=…
2022/7/31 23:38:52 人评论 次浏览 -
字符串
哈希与哈希表 • 使用一个哈希函数将某个特定的数字变成另一个数字，这种操作称之为hash。 • 通常我们会以取模运算来作为哈希函数。 • 举例： hash(key)=key%23, 这样数组 [1 ,75,324] -> [1 ,6,2] • 如果哈希后得到的值相同，我们则可用该值建一个链表，把相同的值…
2022/7/30 6:25:06 人评论 次浏览 -
[luogu4429]染色
显然每一个连通块独立，不妨假设原图连通，并建立dfs树 假设树上有$k$条返祖边，并记其覆盖的点集分别为$V_{1},V_{2},...,V_{k}$ 显然有奇环时无解，因此不妨假设$\forall 1\le i\le k,|V_{i}|\equiv 0(mod\ 2)$，进而$|V_{i}|\ge 4$ 结论：恒有解$\iff \forall 1\le i&l…
2022/7/7 23:23:34 人评论 次浏览 -
省选模板
tarjan 缩强连通分量Graph G; int dfn[N],low[N],dfscnt; int stack[N],top; int scc[N],scccnt; void tarjan(int u){dfn[u]=low[u]=++dfscnt;stack[top++]=u;for(int v,i=G.fir[u];i;i=G.nex[i]){v=G.to[i];if(!dfn[v]){tarjan(v);low[u]=std::min(low[u],low[v]);}else…
2022/6/17 23:20:34 人评论 次浏览 -
Tarjan的一些学习心得与错误
Tarjan的一些学习心得与错误 在原始 \(Tarjan\) 的模板代码中， \(low\) 的处理一般是像下面这样： inline void Tarjan(int u){dfn[u]=low[u]=++tim;GOGRA(e,head,u,i){int v=e[i].to;if(vis[v]==0){Tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v]==1){low[u]=min…
2022/4/18 23:12:41 人评论 次浏览 -
注意事项
语言运算符的优先级：四则运算 \(>\) 关系运算 \(>\) 位运算 \(>\) 逻辑运算。 输出：尽量少混用；puts 会自动换行。 数组：尽量开最大使用\(+ 7\)。 局部变量要初始化。 memset 尽量只初始化 \(0\) 和 \(-1\)。 STL：无关紧要的少用（如存图，stack）。算法Tar…
2022/3/8 23:17:58 人评论 次浏览 -
Tarjan算法
Tarjan 算法简介 Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。 我们定义： 如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连…
2022/3/5 20:45:10 人评论 次浏览 -
【模拟赛】乌拉~~（重链剖分）
背景大家好，我是一名勇敢的俄罗斯士兵，我昨天正在打 CodeForces\tt CodeForcesCodeForces 呢，突然被拉去打仗了。我们已经突入基辅，但因为推进过于迅速，后勤补给未能补上，我们现在急需 143 元来购买一些吃的 一个能替代通信员的老兄来解密一下临时截获的乌克兰电报，…
2022/2/25 23:52:11 人评论 次浏览 -
2022.2.21蓝桥杯准备训练
时隔多年，再次入坑算法竞赛。。。。。 今天复习了点双，边双，割边缩点，割点缩点，强联通分量。 在强联通分量板题中，注意tarjan中的写法 if(!dfn[t]){tarjan(t);low[x] = min(low[x],low[t]);}else if(ins[t]){low[x] = min(low[x],dfn[t]);}而不是 if(!dfn[t]){dfs(t…
2022/2/22 0:01:30 人评论 次浏览 -
tarjan2
反过来调过去，我还是感觉没学明白缩点讲一个有向图中的所有强连通分量缩成一个点后，构成的新图是一个DAG。 一个点所在的强连通分量一定被该点所在DFS搜索树所包含 树上的边大致分为：树枝边，前向边（从上往下指），后向边（从下往上指），横叉变。其中前向边肉眼可见地…
2022/2/15 23:13:44 人评论 次浏览 -
轻重链剖分
目录轻重链剖分轻重链剖分基本原理代码实现（板子）题面换根影响轻重链剖分链操作子树操作整体代码树剖完就是线段树题了qwq没了题外话 轻重链剖分 论文鸽说叫 heavy-light decomposition 或 heavy path decomposition . 正确叫法（不是）：这是真的：轻重链剖分基本原理 …
2022/2/5 6:13:56 人评论 次浏览 -
C++基础：图的连通性算法
目录一.割点和点双连通分量 1.割点 2.点双连通图（点双） 3.点双连通分量（点双）二.桥和边双连通分量 1.桥 2.边双连通图（边双）3.边双连通分量（边双）4.强连通分量(代码单独为一博文)二.连通性的理解 三.求割点与点双连通分量 三.桥和边双连通分量一.割点和点双连通分…
2022/1/30 1:05:29 人评论 次浏览 -
[SDOI2018]战略游戏
\(\text{Solution}\) 问题的转化，建成圆方树后，变为询问 \(S\) 在圆方树上对应的连通子图中的圆点个数减去 \(|S|\) 而根据 \(\text{SDOI2015 寻宝游戏}\) 里的一个重要结论 包含 \(S\) 的极小连通子图边权和的两倍等于将 \(S\) 里的点按 \(dfs\) 序排序后 \(dis(a_1,a_…
2022/1/25 23:09:00 人评论 次浏览
