POJ - 1966 Cable TV Network (最大流求点连通度)
题意：求一个无向图的点连通度。点联通度是指，一张图最少删掉几个点使该图不连通；若本身是非连通图，则点连通度为0。分析：无向图的点连通度可以转化为最大流解决。方法是：1.任意选择一个点作为源点；2.枚举所有与该点间没有边的点作为汇点；3.将每个点拆为入点和出点，入点到出点建一条流量为1的边；4.原本有...
强连通分量(Tarjan)模板
贴模板，备忘。模板1: #include<iostream> #include<cstring> #include<cmath> #include<cstdlib> #include<cstdio> #include<algorith...
UOJ #146. 【NOIP2015】信息传递 连通分量 tarjan模板题
http://uoj.ac/problem/146题解：强连通分量 tarjan模板题。同时试了一下codeblock#include<bits/stdc++.h>using namespace std;const int maxn=2e5+;vector<int> E[ma...
HDU 1317(Floyd判断连通性+spfa判断正环)
XYZZYTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4421 Accepted Submission(s): 1252Probl...
matlab函数_连通区域
1、 matlab函数bwareaopen──删除小面积对象格式：BW2 = bwareaopen(BW,P,conn)作用：删除二值图像BW中面积小于P的对象，默认情况下使用8邻域。算法：(1)Determine the connected components. L = bwlabeln(BW...
[双连通分量] POJ 3177 Redundant Paths
Redundant PathsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 13712 Accepted: 5821DescriptionIn order to get from one of the F (1 <= F &...
POJ 3177 Redundant Paths（边双连通的构造）
Redundant PathsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 13717 Accepted: 5824Description In order to get from one of the F (1 <= F ...
POJ 3177 Redundant Paths & POJ 3352 Road Construction（双连通分量）
DescriptionIn order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of...
POJ 3177——Redundant Paths——————【加边形成边双连通图】
Redundant PathsTime Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uSubmit Status Practice POJ 3177DescriptionIn order to g...
poj 3177 Redundant Paths【求最少添加多少条边可以使图变成双连通图】【缩点后求入度为1的点个数】
Redundant PathsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 11047 Accepted: 4725DescriptionIn order to get from one of the F (1 <= F &...
POJ - 3177 Redundant Paths（边双连通分支）（模板）
1、给定一个连通的无向图G，至少要添加几条边，才能使其变为双连通图。2、3、//边双连通分支/*去掉桥，其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为（leaf+1）/2（leaf为叶子结点的个数）POJ 3177 给定一个...
【强连通分量+spfa】Bzoj1179 Apio2009 Atm
DescriptionSolution显然缩强连通分量，然后求最长路，虽然是DAG但还是有点麻烦，于是用了spfa。Code重建图_数组写错好多次，感觉做这题也就是练了一下实现。 #include<cstdio> #include<algorithm> using names...
[BZOJ1179][APIO2009][强连通分量Tarjan+spfa]ATM
[BZOJ1179][APIO2009]ATMInput第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一...
poj2762 强连通+拓扑序
题意：有 n 个房间，不同房间之间有单向通道，问是否任意两个房间 A 、B 都可以从 A 到 B 或从 B 到 A（有一条有就可以）。在这题中，如果一些点是在同一个强连通分量中，那么这些点肯定能够相互到达，并且如果其他的点到达这里的任意一点，也就可以到达强连通分量中的所有点，所以首先需要对这题进行缩...
poj 3352 Road Construction(边双连通分量+缩点)
题目链接：http://poj.org/problem?id=3352这题和poj 3177 一样，参考http://www.cnblogs.com/frog112111/p/3367039.htmlAC代码： #include<cstdio> #include<cstring&g...
ZOJ 3781 Paint the Grid Reloaded（DFS连通块缩点+BFS求最短路）
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5268题目大意：字符一样并且相邻的即为连通。每次可翻转一个连通块X(O)的颜色，问至少改变几次使得图上所有字符都相等。解题思路：1) dfs( 建图 ) ,因为翻转的时候...
4612 warm up tarjan+bfs求树的直径（重边的强连通通分量）忘了写了，今天总结想起来了。
问加一条边，最少可以剩下几个桥。先双连通分量缩点，形成一颗树，然后求树的直径，就是减少的桥。本题要处理重边的情况。如果本来就两条重边，不能算是桥。还会爆栈，只能C++交，手动加栈了别人都是用的双连通分量，我直接无向图改成有向图搞得强连通水过。 #pragma comment(linker, "/ST...
poj3177（边双连通分量+缩点）
传送门：Redundant Paths题意：有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。分析：在同一个边双连通分量中，任意两...
关于最小生成树，拓扑排序、强连通分量、割点、2-SAT的一点笔记
关于最小生成树，拓扑排序、强连通分量、割点、2-SAT的一点笔记前言：近期在复习这些东西，就xjb写一点吧。当然以前也写过，但这次偏重不太一样MST最小瓶颈路：u到v最大权值最小的路径。在最小生成树上。是次小生成树的一个子问题qwq最小极差生成树：枚举最小生成树上的最小权值的大小topo sort应...
Instantaneous Transference(强连通分量及其缩点)
http://poj.org/problem?id=3592题意：给出一个n*m的矩阵，左上角代表起始点，每个格子都有一定价值的金矿，其中‘#’代表岩石不可达，‘*’代表时空门可以到达指定格子，求出可以获得的最大价值。思路：时空门的存在可能会使得图中出现环，所以先对强连通分量进行缩点，然后对于缩点后...