POJ 3592 Instantaneous Transference（强连通+DP）
POJ 3592 Instantaneous Transference题目链接题意：一个图。能往右和下走，然后有*能够传送到一个位置。'#'不能走。走过一个点能够获得该点上面的数字值，问最大能获得多少思路：因为有环先强连通缩点。然后问题转化为dag，直接dp就可以代码：#include <cs...
King's Quest - poj 1904（强连通分量+外挂输入输出）
题意：国王有N个儿子，每个儿子都有很多喜欢的姑娘，官员为每个王子都找了一个姑娘让他们结婚，不过国王不满意，他想知道他的每个儿子都可以和那个姑娘结婚（前提他的儿子必须喜欢那个姑娘）分析：因为最下面一行已经给出来每个王子可以结婚的对象了，所以就不必在去求完备匹配了，直接加入反边求出来环就行了，不过注意环...
UVA 572 -- Oil Deposits（DFS求连通块+种子填充算法）
UVA 572 -- Oil Deposits（DFS求连通块）图也有DFS和BFS遍历，由于DFS更好写，所以一般用DFS寻找连通块。下述代码用一个二重循环来找到当前格子的相邻8个格子，也可用常量数组或者写8条DFS调用。下述算法是：种子填充（floodfill）两种连通区域四连通区域：从区域内一...
基于visual Studio2013解决算法导论之050强连通分支
题目强连通分支解决代码及点评// 强连通分支.cpp : 定义控制台应用程序的入口点。//#include<iostream>#define MAX 100using namespace std;//深度搜索访问节点层次标志枚举变量enum Color{white,gray,bla...
UVA 247 电话圈 （floyd传递闭包 + dfs输出连通分量的点）
题意：输出所有的环；思路：数据比较小，用三层循环的floyd传递闭包（即两条路通为1，不通为0，如果在一个环中，环中的所有点能互相连通），输出路径用dfs，递归还没有出现过的点（vis），输出并递归该点与其他点能互达的点； #include <cstdio> #include <v...
7-6-有向图强连通分量的Kosaraju算法-图-第7章-《数据结构》课本源码-严蔚敏吴伟民版
课本源码部分第7章 图 - 有向图强连通分量的Kosaraju算法——《数据结构》-严蔚敏.吴伟民版 源码使用说明 链接☛☛☛ 《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明 课本源码合辑 链接☛☛☛ 《数据结构》课本源码合辑 习题集...
tarjan求强连通分量+缩点+割点以及一些证明
“tarjan陪伴强联通分量生成树完成后思路才闪光欧拉跑过的七桥古塘让你 心驰神往”----《膜你抄》 自从听完这首歌，我就对tarjan开始心驰神往了，不过由于之前水平不足，一直没有时间学习。这两天好不容易学会了，写篇博客，也算记录一下。 一、tarjan求强连通分量1、什么是强连通分量？引用来自...
Strongly connected(hdu4635（强连通分量）)
/*http://acm.hdu.edu.cn/showproblem.php?pid=4635Strongly connectedTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) ...
使用PsPing测试Azure虚拟机的连通性
Azure虚拟机启动后，如果在个人的PC上ping该虚拟机的public IP，会出现Request time out的信息，无法ping通。这是因为在 Azure 中，ICMP 包无法通过防火墙和负载均衡器，所以不能直接使用 ping 来测试 Azure 中的虚拟机和服务的连通性。PsPing 是...
poj3352添加多少条边可成为双向连通图
Road ConstructionTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 13311 Accepted: 6715DescriptionIt's almost summer time, and that means that...
js判断网络连通性
js判断网络连通性if (window.navigator.onLine == true) { console.log("首次 -- 已连接") $.ajax({ ...
最大半连通子图 bzoj 1093
最大半连通子图【问题描述】一个有向图G = (V,E)称为半连通的(Semi-Connected)，如果满足：∀ u, v ∈V，满足u—>v 或 v —> u，即对于图中任意两点u,v, 存在一条u到v的有向路径或者从v到u的有向路径。若满足，则称G’是G的一个导出子图。若G’是G的导...
求双连通分量的详解。（根据刘汝佳的训练指南p314）
先看如下的两个定义：点-双连通图：一个连通的无向图内部没有割点，那么该图是点-双连通图。 注意：孤立点，以及两点一边这两种图都是点-双连通的，因为它们都是内部无割点。边-双连通图：一个连通的无向图内部没有桥，那么该图就是边-双连通图。 注意：孤立点是边-双连通的，但是两点...
hdoj 3072 Intelligence System【求scc&&缩点】【求连通所有scc的最小花费】
Intelligence SystemTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1904 Accepted Submission...
LightOJ1417 Forwarding Emails（强连通分量+缩点+记忆化搜索）
题目大概是，每个人收到信息后会把信息发给他认识的一个人如此下去，问一开始要把信息发送给谁这样看到信息的人数最多。首先找出图中的SCC并记录每个SCC里面的点数，如果传到一个SCC，那么里面的人都可以看到信息。然后SCC缩点后就形成DAG，直接记忆化搜索，d(u)搜索从u点出发开始传最多能传多少人。最...
poj 3694 Network 边双连通+LCA
题目链接：http://poj.org/problem?id=3694题意：n个点，m条边，给你一个连通图，然后有Q次操作，每次加入一条边（A,B），加入边后，问当前还有多少桥，输出桥的个数。解题思路：先将原连通图边双连通缩点成一颗树，Q次操作过程中对树进行LCA操作。具体看代码：看网上也有不缩点的...
POJ - 3177 Redundant Paths （边双连通缩点）
题意：在一张图中最少可以添加几条边，使其中任意两点间都有两条不重复的路径（路径中任意一条边都不同）。分析：问题就是最少添加几条边，使其成为边双连通图。可以先将图中所有边双连通分量缩点，之后得到的就是一棵树。那么问题又转化成为：在这棵树上添加几条边使其成为一个双连通分量。答案是缩点之后（leaf+1）...
POJ3352 Road Construction Tarjan+边双连通
题目链接：http://poj.org/problem?id=3352题目要求求出无向图中最少需要多少边能够使得该图边双连通。在图G中，如果任意两个点之间有两条边不重复的路径，称为“边双连通”，去掉任何一条边都是其他边仍然是连通的，也就是说边双连通图中没有割边。算法设计是：运用tarjan+缩点。对...
poj 3177 Redundant Paths（tarjan边双连通）
题目链接：http://poj.org/problem?id=3177题意：求最少加几条边使得没对点都有至少两条路互通。题解：边双连通顾名思义，可以先求一下连通块显然连通块里的点都是双连通的，然后就是各个连通块之间的问题。也就是说只要求一下桥，然后某个连通块桥的个数位1的总数，结果就是（ans+1）...
poj3177--Redundant Paths（边的双连通）
有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。一个连通无向图最少加几条边变成双连通图(缩点后叶子节点（即度数为1）的个数 + ...