【图论】双连通总结

双连通总结

这类问题分为,边-双连通,点-双连通

边双连通

边双连通,求出来后,连接没一个双连通的分量的就是割边,因此可以缩点成一棵树,把问题转化为在树上搞,割边的定义为:去掉这条边后图将不连通

基本这类题都一个解法,求双连通分量,然后缩点成树,进行操作

或者就是直接要求割边,做跟割边相关的操作

模板:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10005;
const int M = 20005;

int n, m, val[N];

struct Edge {
	int u, v, id;
	bool iscut;
	Edge() {}
	Edge(int u, int v, int id) {
		this->u = u;
		this->v = v;
		this->id = id;
		this->iscut = false;
	}
} edge[M * 2], cut[M];

int en, first[N], next[M], cutn;

void init() {
	memset(first, -1, sizeof(first));
	en = 0;
}

void add_edge(int u, int v, int id) {
	edge[en] = Edge(u, v, id);
	next[en] = first[u];
	first[u] = en++;
}

int pre[N], dfn[N], bccno[N], bccn, dfs_clock;

void dfs_cut(int u, int fa) {
	pre[u] = dfn[u] = ++dfs_clock;
	for (int i = first[u]; i + 1; i = next[i]) {
		int v = edge[i].v;
		if (edge[i].id == fa) continue;
		if (!pre[v]) {
			dfs_cut(v, edge[i].id);
			dfn[u] = min(dfn[u], dfn[v]);
			if (dfn[v] > pre[u]) {
				edge[i].iscut = edge[i^1].iscut = true;//标记割边
				cut[cutn++] = edge[i];//存放割边
			}
		} else dfn[u] = min(dfn[u], pre[v]);
	}
}

void find_cut() {
	dfs_clock = cutn = 0;
	memset(pre, 0, sizeof(pre));
	for (int i = 0; i < n; i++)
		if (!pre[i]) dfs_cut(i, -1);
}

void dfs_bcc(int u) {
	pre[u] = 1;
	bccno[u] = bccn;
	for (int i = first[u]; i + 1; i = next[i]) {
		if (edge[i].iscut) continue;
		int v = edge[i].v;
		if (pre[v]) continue;
		dfs_bcc(v);
	}
}

vector<int> bcc[N];

void find_bcc() {
	bccn = 0;
	memset(pre, 0, sizeof(pre));
	for (int i = 0; i < n; i++) {
		if (!pre[i]) {
			dfs_bcc(i);
			bccn++;
		}
	}
}

int main() {

	return 0;
}

HDU 2242 考研路茫茫——空调教室 边双连通缩点+dfs

HDU 2460 Network 边双连通缩点+树链剖分

HDU 3849By Recognizing These Guys, We Find Social Networks Useful 求桥

HDU 4005 The war 边双连通缩点+dfs

HDU 3394 Railway 双连通求块

3177 Redundant Paths 构造边双连通,利用度数去求

3352 Road Construction 构造边双连通,利用度数去求

1515 Street Directions 无向图改有向图,双连通内部肯定都能改,桥不能改

1438 One-way Traffic 混合图改有向图(这题的数据貌似有点问题)

点双连通

点双连通,求出来个,连接的是割点,注意一个割点可能属于不同的点-双连通分量,割点定义为:去掉这个点后,图将不连通

模板:

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 1005;
const int M = 2000005;
int n, m;

struct Edge {
	int u, v;
	Edge() {}
	Edge(int u, int v) {
		this->u = u;
		this->v = v;
	}
} edge[M];

int first[N], next[M], en;

void add_edge(int u, int v) {
	edge[en] = Edge(u, v);
	next[en] = first[u];
	first[u] = en++;
}

void init() {
	en = 0;
	memset(first, -1, sizeof(first));
}

int pre[N], dfn[N], bccno[N], dfs_clock, bccn;
bool iscut[N];

stack<Edge> S;
vector<int> bcc[N];

void dfs_bcc(int u, int fa) {
	dfn[u] = pre[u] = ++dfs_clock;
	int child = 0;
	for (int i = first[u]; i + 1; i = next[i]) {
		int v = edge[i].v;
		if (fa == v) continue;
		if (!pre[v]) {
			S.push(edge[i]);
			child++;
			dfs_bcc(v, u);
			dfn[u] = min(dfn[u], dfn[v]);
			if (dfn[v] >= pre[u]) {
				iscut[u] = true;
				bccn++;
				bcc[bccn].clear();
				while (1) {
					Edge x = S.top(); S.pop();
					if (bccno[x.u] != bccn) {bcc[bccn].push_back(x.u); bccno[x.u] = bccn;}
					if (bccno[x.v] != bccn) {bcc[bccn].push_back(x.v); bccno[x.v] = bccn;}
					if (x.u == u && x.v == v) break;
				}
			}
		} else if (pre[v] < pre[u] && v != fa) {
			S.push(edge[i]);
			dfn[u] = min(dfn[u], pre[v]);
		}
	}
	if (fa == 0 && child == 1) iscut[u] = 0;
}

void find_bcc() {
	memset(pre, 0, sizeof(pre));
	memset(bccno, 0, sizeof(bccno));
	memset(iscut, false, sizeof(iscut));
	dfs_clock = bccn = 0;
	for (int i = 1; i <= n; i++)
		if (!pre[i]) dfs_bcc(i, 0);
}

POJ 2942 Knights of the Round Table 点双连通经典题,利用点双连通和二染色去做

UVA 1108 Mining Your Own Business 点双连通分量+计数

时间: 10-26

【图论】双连通总结的相关文章

图的连通性问题的小结 (双连通、2-SAT)

图的连通性问题包括: 1.强连通分量. 2.最小点基和最小权点基. 3.双连通. 4.全局最小割. 5.2-SAT 一.强连通分量 强连通分量很少单独出题,一般都是把求强连通分量作为缩点工具. 有三种算法: 1.Kosaraju算法.对原图和反图分别进行一次深度优先搜索. 2.Tarjan算法.用了时间戳. 3.Garbow算法.与Tarjan算法是同一思想,但更精妙. 三种算法的模版我已经贴过了  http://www.cnblogs.com/Potato-lover/p/3956604.ht

HDU 4005 The war(双连通好题)

HDU 4005 The war 题目链接 题意:给一个连通的无向图,每条边有一个炸掉的代价,现在要建一条边(你不不知道的),然后你要求一个你需要的最少代价,保证不管他建在哪,你都能炸掉使得图不连通 思路:炸肯定要炸桥,所以先双连通缩点,得到一棵树,树边是要炸的,那么找一个最小值的边,从该边的两点出发,走的路径中,把两条包含最小值的路径,的两点连边,形成一个环,这个环就保证了最低代价在里面,除了这个环以外的最小边,就是答案,这样的话,就利用一个dfs,搜到每个子树的时候进行一个维护即可 代码:

ACM学习-图双连通子图

// ACM学习-割点和桥.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; const int v = 13; int edge[v][v] = { { 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0

双连通问题

一些定义: 割点集合(割集):在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合. 点连通度:最小割点集合中的顶点数. 割边集合:如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合. 边连通度:最小割边集合中的边数. 点双连通:如果一个无向连通图的点连通度大于1,则称该图是点双连通的,简称双连通或重连通.割点:一个图有割点,当且仅当这个图的点连通度为1,则割点集合的唯一元素被称为

poj1515--Street Directions(边的双连通)

给一个无向图,要求变成强连通的有向图,需要保留哪些边. 边的双连通,对于桥保留两条边,其他的只保留一条边.求双连通的过程中记录保留边. /********************************************* Problem: 1515 User: G_lory Memory: 232K Time: 32MS Language: C++ Result: Accepted **********************************************/ #incl

poj3352Road Construction 边双连通+伪缩点

/* 对于边双连通分支,求法更为简单.只需在求出所有的桥以后,把桥边删除,原图变成了多个连通块,则每个连通块就是一个边双连通分支.桥不属于任何 一个边双连通分支,其余的边和每个顶点都属于且只属于一个边双连通分支. 一个有桥的连通图,如何把它通过加边变成边双连通图?方法为首先求出所有的桥, 然后删除这些桥边,剩下的每个连通块都是一个双连通子图.把每个双连通子图收缩为一个顶点, 再把桥边加回来,最后的这个图一定是一棵树,边连通度为1. 统计出树中度为1的节点的个数,即为叶节点的个数,记为leaf.则

割点、桥模板以及点双连通、边双连通

一.概念 概念: 1.桥: 如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边u为G的桥,又称割边或关节边. 2.割点:如果在图G中删去一个结点u后,图G的连通分枝数增加,即W(G-u)>W(G),则称结点u为G的割点,又称关节点. 3.点双连通分量:不含割点的连通子图 4.边双连通分量:不含割边的连通子图 性质: 1.边双连通分量中,任意两点都在某个边环中.(任意两点不一定在点环中) 2.点双连通分量中,任意两点都在某个点环中. 3.点双连通分量不一定是边双连

poj 3352 Road Construction【边双连通求最少加多少条边使图双连通&amp;&amp;缩点】

Road Construction Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 10141   Accepted: 5031 Description It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the r

POJ3352Road Construction(边的双连通+强连通缩点)

Road Construction Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8673   Accepted: 4330 Description It's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the ro