无向图——双连通分量

    双连通图：在无向图连通图中，如果删除该图中的任意一点和依附它的边，不改变图的连通性，则称该图为双连通的无向图。

    由上述定义可知，双连通分量中，每两个结点之间至少有两条不同的路径可以相互到达。

    割点：在无向连通图中删去某个点a和依附a的边，图变为不连通，则该点称为割点，也叫关节点。

    割边：在无向连通图中删去某条边，图变为不连通，则该边称为割边，也叫桥。

    点双连通分支(块)与边双连通分支：

点双连通分支与边双连通分支是两个完全不同的概念。割点可以存在多个点连通分支中(相反，桥就不一样)。一个图可以有割点而没有割边，也可以有割边而没有割点。

 

点双连通分支的求法和边双连通分支的求法类似，不过在出栈的地方有些不同。下面介绍几个例子。

 

POJ3177(3352)

题目大意：最少需要加多少条边使得原图变为双连通图（原图连通）。

解：求桥(注意平行边)，在求桥的过程中缩点，利用并查集，将每个连通分量用一个点代表。将这些代表用桥连接起来，就构成了一颗树。统计树中度数为1的点(即叶子结点)的个数count，将叶子结点两两相连，则添加边的数量为(count+1)/2。

#include <iostream>
const int MAX = 5002;

int p[MAX];
struct Graph
{
	int to;
	int next;
}e[MAX*4];
int index[MAX];
int edgeNum;
int seq;

int low[MAX];		//low[u]表示在树中从u点出发，经过一条其后代组成的路径和回退边，所能到达的最小深度的顶点标号
int dfn[MAX];		//dfn[u]表示结点u在树中的编号
int bridge[MAX][2],bridge_n;
int degree[MAX];
int n,m;

int min(int x, int y)
{
	return x < y ? x : y;
}

void makeSet()
{
	for(int i = 1; i <= n; i++)
		p[i] = i;
}

int findSet(int x)
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void Union(int x, int y)
{
	x = findSet(x);
	y = findSet(y);
	if(x == y)
		return;
	p[y] = x;
}

void addEdge(int from, int to)
{
	e[edgeNum].to = to;
	e[edgeNum].next = index[from];
	index[from] = edgeNum++;
	e[edgeNum].to = from;
	e[edgeNum].next = index[to];
	index[to] = edgeNum++;
}

//边连通分量，求桥
void bridge_dfs(int u, int v)
{
	int repeat = 0;					//有平行边
	low[u] = dfn[u] = seq++;
	for(int i = index[u]; i != -1; i = e[i].next)
	{
		int w = e[i].to;
		if(w == v)
			repeat++;
		if(dfn[w] < 0)
		{
			bridge_dfs(w,u);
			low[u] = min(low[u],low[w]);
			if(!(low[w] > dfn[u]))		//不是桥，缩点
			{
				Union(w,u);
			}
			else
			{
				bridge[++bridge_n][0] = u;
				bridge[bridge_n][1] = w;
			}
		}
		else if(v != w || repeat != 1)    //重要
			low[u] = min(low[u],dfn[w]);
	}
}

int solve()
{
	int i,j;
	int a,b;
	int count = 0;
	memset(degree,0,sizeof(degree));
	for(i = 1; i <= bridge_n; i++)
	{
		a = findSet(bridge[i][0]);
		b = findSet(bridge[i][1]);
		degree[a]++;
		degree[b]++;
	}
	for(i = 1; i <= n; i++)
		if(degree[i] == 1)
			count++;
	return (count+1)/2;
}

int main()
{
	int i,j;
	int a,b;
	edgeNum = 0;
	seq = 0;
	bridge_n = 0;
	memset(index,-1,sizeof(index));
	memset(dfn,-1,sizeof(dfn));
	scanf("%d %d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d %d",&a,&b);
		addEdge(a,b);
	}
	makeSet();
	bridge_dfs(1,-1);
	printf("%d\n",solve());
	return 0;
}

 

POJ2942

题目大意：有n个骑士，骑士一段时间要坐在圆桌上举行高级会议，但要满足条件：互相憎恨的骑士不能相邻，圆桌上的人数必须是大于1的奇数。现在给出骑士之间的憎恨关系，问至少有多少个骑士要被排除在外。

解：首先建补图，这样骑士a和骑士b之间有连线，说明a和b可以相邻。还可以想到奇环，不在任何奇环的骑士将被排除。问题是如何求图中的奇环？这里有一个定理：双连通分量中如果存在奇环，那么整个分量的点全部包含在奇环中(自己体会)。这样，可以先求点的双连通分量，判断每个双连通分量是否包含奇环(用染色，若相邻点颜色相同，存在奇环)，若存在奇环，则该分量包含的骑士都不会被排除。

#include <iostream>
const int MAX = 1001;
int n,m;
//若某块(双连通分量)不可染色为二分图，则该块存在奇圈；若某块存在奇圈，那么该块中的所有点都存在与奇圈中；
//那么答案就是所有不在任何奇圈中的骑士的个数。
bool map[MAX][MAX];
int dfn[MAX],low[MAX],stack[MAX];
int top,seq,result;
bool b[MAX],used[MAX];
int color[MAX];

int min(int x, int y)
{
	return x < y ? x : y;
}

bool isOk(int v, int col)
{
	color[v] = col;
	for(int w = 1; w <= n; w++)
	{
		if(map[v][w])
		{
			if(b[w])
			{
				if(color[v] == color[w])	//相邻两点颜色相同，构不成二分图，含奇圈
					return true;
				if(color[w] == -1)
					isOk(w, col^1);
			}
		}
	}
	return false;
}

void dummy(int t, int *a)
{
	int i,j;
	memset(b,0,sizeof(b));	//b[i]=1表示结点i属于当前的双连通分量中
	for(i = 0; i < t; i++)
		b[a[i]] = true;
	for(i = 0; i < t; i++)
	{
		memset(color,-1,sizeof(color));
		if(isOk(a[i],1))
			break;
	}
	if(i < t)		//含奇圈
	{
		for(j = 0; j < t; j++)
		{
			if(!used[a[j]])
			{
				result++;
				used[a[j]] = true;
			}
		}
	}
}

void bicon(int u)
{
	int a[MAX];
	low[u] = dfn[u] = seq++;
	stack[top] = u;
	top++;
	for(int w = 1; w <= n; w++)
	{
		if(map[u][w])
		{
			if(dfn[w] < 0)					//第一种情况，w是新点
			{
				bicon(w);
				low[u] = min(low[u],low[w]);
				if(low[w] >= dfn[u])		//u割点(把割点留在栈中) 
				{
					int k = 1;
					a[0] = u;
					do
					{
						--top;
						a[k++] = stack[top];
					}while(stack[top] != w);
					dummy(k,a);
				}
			}
			else					//u,w是回边(w是u的祖先)
				low[u] = min(low[u],dfn[w]);
		}
	}
}

void block()
{
	for(int i = 1; i <= n; i++)
		if(dfn[i] < 0)
			bicon(i);
}

int main()
{
	int i,j;
	int a,b;
	while(true)
	{
		scanf("%d %d",&n,&m);
		if(n == 0 && m == 0)
			break;
		memset(map,1,sizeof(map));
		memset(dfn,-1,sizeof(dfn));
		memset(used,0,sizeof(used));
		seq = 0;
		top = 0;
		result = 0;
		for(i = 0; i < m; i++)
		{
			scanf("%d %d",&a,&b);
			map[a][b] = false;
			map[b][a] = false;
		}
		for(i = 1; i <= n; i++)
			map[i][i] = false;
		block();
		printf("%d\n",n - result);
	}
	return 0;
}

 

POJ3694

题目大意：给定一个初始的网络，每次(1000次)向网络里加一条边，问网络中桥的数量。(网络是动态的)

解：这题难就难在网络是动态的，如果是静态，可以用边的双连通分量来直接求解。简单的想法是每修改一次就重新计算一次，但是这样超时。联想：通过缩点，缩点之间用桥连接，形成一颗树，树边就是桥，桥的总数为sum。每次向网络里加一条边a,b，先用并查集找出a和b所属的树的结点，显然，a和b到ab的最近公共祖先这条路径上的桥全部无效。这样，每次只需在树上操作sum--。这样复杂度就降下来了。

#include <iostream>
const int MAX = 100002;
int n,m;
int result;
struct Edge
{
	int to;
	int next;
}e[MAX*10],tree[MAX*10];
int index[MAX],index2[MAX],edgeNum,edgeT;
int seq;

int low[MAX],dfn[MAX];
int p[MAX],res[MAX];
int level[MAX],pre[MAX];
bool vis[MAX],bridge[MAX];

int min(int x, int y)
{
	return x < y ? x : y;
}

void addEdge(int from, int to)
{
	e[edgeNum].to = to;
	e[edgeNum].next = index[from];
	index[from] = edgeNum++;
}

void addTree(int from, int to)
{
	tree[edgeT].to = to;
	tree[edgeT].next = index2[from];
	index2[from] = edgeT++;
}

void makeSet()
{
	for(int i = 1; i <= n; i++)
		p[i] = i;
}

int findSet(int x)
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void Union(int x, int y)
{
	x = findSet(x);
	y = findSet(y);
	if(x == y)
		return;
	p[x] = y;
}

void bridge_dfs(int u, int v)
{
	int repeat = 0;
	low[u] = dfn[u] = seq++;
	for(int i = index[u]; i != -1; i = e[i].next)
	{
		int w = e[i].to;
		if(v == w)
			repeat++;
		if(dfn[w] < 0)
		{
			bridge_dfs(w,u);
			low[u] = min(low[u],low[w]);
			if(low[w] > dfn[u])
			{
				result++;
				res[result] = i;
				//bridge[w] = 1;
			}
			else
				Union(w,u);
		}
		else if(v != w || repeat != 1)
			low[u] = min(low[u],dfn[w]);
	}
}

void lca_dfs(int u, int deep)
{
	for(int i = index2[u]; i != -1; i = tree[i].next)
	{
		int v = tree[i].to;
		if(!vis[v])
		{
			vis[v] = true;
			pre[v] = u;
			level[v] = deep+1;
			lca_dfs(v,deep+1);
		}
	}
}

void lca(int u, int v)
{
	while(level[u] > level[v])
	{
		if(bridge[u])
		{
			result--;
			bridge[u] = 0;
		}
		u = pre[u];
	}
	while(level[v] > level[u])
	{
		if(bridge[v])
		{
			result--;
			bridge[v] = 0;
		}
		v = pre[v];
	}
	while(u != v)
	{
		if(bridge[u])
		{
			bridge[u] = 0;
			result--;
		}
		if(bridge[v])
		{
			bridge[v] = 0;
			result--;
		}
		u = pre[u];
		v = pre[v];
	}
}

int main()
{
	int i,j;
	int a,b;
	int q;
	int cases = 1;
	while(true)
	{
		scanf("%d %d",&n,&m);
		if(n == 0 && m == 0)
			break;
		edgeNum = 0;
		edgeT = 0;
		result = 0;
		seq = 0;
		memset(index,-1,sizeof(index));
		memset(index2,-1,sizeof(index2));
		memset(dfn,-1,sizeof(dfn));
		memset(vis,0,sizeof(vis));
		memset(level,0,sizeof(level));
		memset(bridge,0,sizeof(bridge));
		makeSet();
		for(i = 0; i < m; i++)
		{
			scanf("%d %d",&a,&b);
			addEdge(a,b);
			addEdge(b,a);
		}
		scanf("%d",&q);
		printf("Case %d:\n",cases++);
		bridge_dfs(1,-1);		//找到边的双连通 缩点
		int x,y;
		for(i = 1; i <= n; i++)	//将缩点集合转化为一颗树
		{
			for(j = index[i]; j != -1; j = e[j].next)
			{
				x = findSet(i);
				y = findSet(e[j].to);
				if(x != y)
					addTree(x,y);
			}
		}
		//
		memset(vis,0,sizeof(vis));
		vis[p[1]] = true;
		level[p[1]] = 1;
		lca_dfs(p[1],1);
		for(i = 1; i <= result; i++)
			bridge[findSet(e[res[i]].to)] = 1;
		while(q--)
		{
			scanf("%d %d",&a,&b);
			a = findSet(a);
			b = findSet(b);
			if(a != b)
				lca(a,b);
			printf("%d\n",result);
		}
		printf("\n");
	}
	return 0;
}