双连通图：在无向图连通图中，如果删除该图中的任意一点和依附它的边，不改变图的连通性，则称该图为双连通的无向图。
由上述定义可知，双连通分量中，每两个结点之间至少有两条不同的路径可以相互到达。
割点：在无向连通图中删去某个点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;
}
分享到：
相关推荐
要求采用邻接矩阵作为无向图的存储结构，邻接表作为有向图的存储结构，完成无向图和有向图的建立，并对建立好的图进行深度和广度优先遍历。具体实现要求： 1. 通过键盘输入图的顶点和边信息，分别构造一个无向图的...
在无向图的DFS过程中，每个顶点会被访问一次且仅一次，最终形成一种特殊的树结构——深度优先森林。在这个森林中，每个连通分量（即图中任意两个顶点都可以通过边到达的子图）都会被表示为一棵树。 在孩子兄弟链表...
在一个无向图中，如果删除任意一条边都不会导致图变为不连通，那么这个连通分量被称为双连通分量。换句话说，双连通分量中的任意两个顶点都存在至少两条互相独立的路径。双连通分量的研究在诸如网络可靠性、数据结构...
双连通分量则是无向图中的一个子集，其中任意两个顶点都是通过一系列非桥边相连的，即使去掉这些边，分量内的顶点依然保持连通。理解双连通分量有助于我们解决许多实际问题，例如在互联网中分析节点的紧密程度，或者...
连通分量是无向图中最大的子图，其中任意两个顶点都是连通的。强连通分量则是有向图中的极大子图，每个顶点都可以通过有向路径到达其他任何顶点。生成树是图的极小连通子图，包含所有顶点但只有一条路径，而生成森林...
一)建立一个无向图+遍历+插入 (1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图； (2)对（1）中生成的无向图进行广度优先遍历并打印结果； (3)向（1）中生成的无向图插入一条...
1. 连通图：如果在一个无向图中，从任一顶点出发可以到达其他所有顶点，那么这个图被称为连通图。连通图可以是简单连通图，即没有自环（一条边的两端为同一个顶点）和重边（两个顶点间有多条边）。例如，一棵树就是...
连通图是无向图中任何两个顶点间都存在路径的情况，其最大连通子图称为连通分量。对于有向图，强连通图是每个顶点对之间都存在双向路径的图，其最大强连通子图是强连通分量。 在图的操作上，常见的有建立和销毁图...
连通图是指在无向图中，任意两个顶点之间都存在路径的图，而连通分量是非连通图的最大连通子图。在有向图中，强连通图是每个顶点都能到达其他任何顶点的图，强连通分量是非强连通图的极大强连通子图。 生成树是连通...
在有向图中，如果从每个顶点都能通过一系列边到达其他所有顶点，那么这些顶点组成一个强连通分量。在一个DAG中，可能存在多个强连通分量，也可能只有一个大的强连通分量或者完全没有强连通分量。找出这些分量对于...
最大连通分量是指在一个无向图中，能够找到的最大子集，其中任意两个节点之间都存在路径相连。在MATLAB中，可以使用内置函数`biconncomp`或`conncomp`来寻找这样的分量。 标题中提到的“最大分量”就是指最大连通...
根据边是否有方向，图可以分为有向图和无向图；根据边是否带有权重，图又可以分为加权图和无权图。在有向图中，边具有方向性，从一个顶点指向另一个顶点；而在无向图中，边没有方向，视为两个顶点之间的连接。 图的...
无向图 完全图 稀疏图 稠密图 权 网 邻接 关联（依附） 顶点的度 有向树 路径 路径长度 回路（环） 简单路径 简单回路（简单环） 连通图 强连通图 子图 连通分量 强连通分量 极小连通子图 生成树 生成森林 图的类型...
- **连通分量**：在无向图中，如果任意两个顶点都是可达的，则称图是连通的。否则，可分成若干个互不相连的子集，每个子集称为一个连通分量。 - **生成树**：无向图的生成树是图的一个子集，包含图中所有的顶点，...
- **割点**: 对于一个无向图，如果删除一个节点后图的连通分量数增加，则称该节点为割点。 - **割边(桥)**: 如果删除一条边后图的连通性受到影响，即图分裂为两个不相连的子图，则称该边为割边。 - **连通性算法**...
* 邻接：在无向图中，如果两个顶点之间存在边，则称这两个顶点是邻接的。 * 依附：在无向图中，如果一个顶点和边相连，则称该顶点依附于该边。 * 无向图：在图中，所有边都是无向的。 * 有向图：在图中，所有边都是...
- **连通分量**：无向图的最大连通子图。 7. **强连通图与强连通分量**： - **强连通图**：有向图中任意两个顶点间都存在双向可达的路径。 - **强连通分量**：有向图的最大强连通子图。 8. **生成树**： - **...
无向图中的边没有方向，而有向图中的边有方向。加权图则为每条边赋予一个数值，代表边的权重或成本。 2. **图的表示**：在程序中，图可以使用邻接矩阵或邻接表来表示。邻接矩阵是二维数组，如果两个顶点之间有边，...
除了求解强连通分量，Tarjan算法还有其他应用，例如在无向图中求解双连通分量。这种算法与求解强连通分量的Tarjan算法有着相似的结构和思想，通过类比和组合理解，可以帮助我们更深入地掌握这两种算法。 总的来说，...