网络安全
保研
scipy
Shell脚本
zabbix
opencv
AOE网
USB
ROBOGUIDE
损失函数
2022
在线聊天系统
VECTOR工具
java-zookeeper
异步
symbol
qt布局管理器
素数
tee
安杰思
tarjan
2024/4/12 2:07:52![bzoj 2208: [Jsoi2010]连通数](http://www.lydsy.com/JudgeOnline/images/2208.jpg)
bzoj 2208: [Jsoi2010]连通数
Description Input 输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。 Output 输出一行一个整数，表示该图的连通数。 Sample Input 3 010 001 100 Sample Outp…
![【题解】P3119 [USACO15JAN] Grass Cownoisseur](/images/no-images.jpg)
【题解】P3119 [USACO15JAN] Grass Cownoisseur
题意
传送门
题意很简单，给定一张有向图，允许选择在一条边上反向行走一次，求从1出发，且最终回到1，最多能遍历到的点数。
Solution
一道综合性的图论好题。
首先想到，对于一个强连通分量内的点…
有向图的强连通性（java）
Kosaraju算法
一句话理解Kosaraju算法：按从终点向起点遍历的顺序遍历有向图，如果能遇到起点，那么就说明该两点之间是强连接关系。
Tarjan算法
package graph.digraph;import java.io.File;
import java.io.FileNotFoundException;
import …
算法随笔：强连通分量
概念和性质： 强连通：在有向图G中，如果两个点u和v是互相可达的，即从u出发可以到达v，从v出发也可以到达u，则成u和v是强连通的。
强连通分量：如果一个有向图G不是强连通图，那么可以把它…
poj2942:Knights of the Round Table（Tarjan）
传送门
题意： 亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置&am…
蓝桥杯 2017 决赛 发现环 (求环内的点)
历届试题 发现环 时间限制：1.0s 内存限制：256.0MB问题描述小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。不过在最…
C++学习笔记：图论——缩点详解
引言
缩点，哲学的东西，你必须拥有。。。 缩点
个人认为就是把一堆强连通的点( 即强连通分量 )，认作为一个点
强连通分量就是这里面的点可以相互到达（算是个环） 详解
一个有向图如下 可以看出有强连通分量 { 1 , 2 …
C++学习笔记：有向图的强连通分量
强连通图分量
首先得知道这是个什么玩意儿，对于一个如下的有向图 在这个有向图G中，如果有两个点可以相互到达，则两点为强连通，若图中每个点都可以相互到达，则图G为强连通图 1. 一个有向图是强连通的，而且仅…
间谍网络（C++，强连通分量，缩点）
题目描述
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以&#x…
poj3678:Katu Puzzle（2-SAT）
传送门
题意
有一个大小为N的集合{x1,x2..xn}，xi0或1，现在给出它们之间的一些逻辑运算的结果(比如x1 and x21)，逻辑运算有AND OR XOR三种，问是否存在一种满足所有条件的取值方案。
题解:2-SAT
这道题真是把2-SAT思想诠释得淋漓…
POJ 1986 Distance Queries Tarjan算法求最近公共祖先+前向星
第一次尝试自己写博客，如果有什么不好的地方还请大家多多批评指正~传送门：POJ 1986题目大意：
John是一个农场主，他的牛都懒散惯了，所以拒绝按照John所选的路走。John就想找一条最短的路。本题输入前半部分与“导航噩梦…
poj1236:Network of School（Tarjan）
Description 一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不必也在 B 学校的列表中。 你要写一个程序计算，…
Tarjan求图的割点、桥与双连通分量
关于Tarjan的部分知识：poj1236:Network of School（Tarjan） 图的割点桥与双连通分量定义点连通度与边连通度双连通图割点与桥双连通分量分支 Tarjan算法求双连通分量例题 图的割点、桥与双连通分量
定义
点连通度与边连通度：
…
Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines
题目大意：
给你n个点，分别位于pi。每个点有个爆炸范围ri和代价ci，花费ci可以引爆某个点，并且pi-ri到piri范围内的点都会被引爆。q个询问，每次修改一个点的ci，每次输出引爆所有店的最小代价。 题解…
poj2749:Building roads（2-SAT）
传送门
题意
有N个农场，其中A对相互讨厌，不能碰面；B对相互喜欢，必须碰面。给定两个中转站S1和S2、各个农场的坐标，让每个农场连接到其中一个中转站。求最小化任意两个农场通过中转站的最大距离，若无法实现…
bzoj 1051: [HAOI2006]受欢迎的牛
Description 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少…
[APIO2018]铁人两项
Description
给出一张n个点，m条边的简单无向图，求有多个三元组(s,f,t)，满足两两互不相等且存在至少一条从s出发经过f到t的不经过重复点的路径。 n<1e5,m<2e5
Solution
考场都去做A了没仔细想C，以为很麻烦 其实把圆方树…
bzoj 1529: [POI2005]ska Piggy banks
Description Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input 第一行一个整数…
C++学习笔记：Tarjan算法剖析——求 强连通分量，割点，割边，点双连通分量，边双连通分量 的详解
Tarjan算法详解
目录
1.Tarjan算法求强连通分量
2. Tarjan算法求割点
3. Tarjan算法求点双连通分量
4. Tarjan算法求割边
5. Tarjan算法求边双连通分量 1.Tarjan算法求强连通分量
了解一下 强连通分量
对于一个有向图的DFS的搜索树（i 可以到 j，j…
Loj10103「一本通 3.6 练习 4」电力
题目传送门
题意
求一个图删除一个点之后，联通块最多有多少。
思路
很显然对于在有割点的情况下，要删除割点，而删除割点后增加的连通块个数可以这样计算：
设num[i]表示第i个点被删除后增加的连通块个数。
当前点x为…
[CF 732F]Tourist Reform
Description
给出一张n个点，m条边的无向联通图，现在你要给每条边一个方向，设f(x)表示x所能到达的点的数量，你需要使得最小的f(x)最大。 求一种方案。 n,m<4*10^5
Solution
这道题一点都不像F题（毕竟div.2&…