标题:
hiho一下 连通性二·边的双连通分量
[打印本页]
作者:
yuyang911220
时间:
2016-8-20 20:10
标题:
hiho一下 连通性二·边的双连通分量
描述在基本的网络搭建完成后,学校为了方便管理还需要对所有的服务器进行编组,网络所的老师找到了小Hi和小Ho,希望他俩帮忙。
老师告诉小Hi和小Ho:根据现在网络的情况,我们要将服务器进行分组,对于同一个组的服务器,应当满足:当组内任意一个连接断开之后,不会影响组内服务器的连通性。在满足以上条件下,每个组内的服务器数量越多越好。
比如下面这个例子,一共有6个服务器和7条连接:
其中包含2个组,分别为{1,2,3},{4,5,6}。对{1,2,3}而言,当1-2断开后,仍然有1-3-2可以连接1和2;当2-3断开后,仍然有2-1-3可以连接2和3;当1-3断开后,仍然有1-2-3可以连接1和3。{4,5,6}这组也是一样。
老师把整个网络的情况告诉了小Hi和小Ho,小Hi和小Ho要计算出每一台服务器的分组信息。
提示:边的双连通分量
输入第1行:2个正整数,N,M。表示点的数量N,边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行:2个正整数,u,v。表示存在一条边(u,v),连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出第1行:1个整数,表示该网络的服务器组数。
第2行:N个整数,第i个数表示第i个服务器所属组内,编号最小的服务器的编号。比如分为{1,2,3},{4,5,6},则输出{1,1,1,4,4,4};若分为{1,4,5},{2,3,6}则输出{1,2,2,1,1,2}
样例输入6 71 21 32 33 44 54 65 6样例输出21 1 1 4 4 4提示:对于一个无向图,当我们把图中所有的桥都去掉以后,剩下的每一个区域就是我们要求的边的双连通分量。比如:
其中{1,2,3},{4,5,6},{7}各为一个组。
直观的做法自然先用上周的算法求出所有桥,去掉所有桥之后再做DFS求出每一个连通子图。我们这周要介绍一种更"抽象"的算法,通过在Tarjan算法当中巧妙地用一个栈来统计出每一个组内的节点,其代码如下:
[cpp]
view plain
copy
void dfs(int u) {
//记录dfs遍历次序
static
int counter = 0;
//记录节点u的子树数
int children = 0;
ArcNode *p = graph
.firstArc;
visit
= 1;
//初始化dfn与low
dfn
= low
= ++counter;
//将u加入栈
stack[++top] = u;
for(; p != NULL; p = p->next) {
int v = p->adjvex;
//节点v未被访问,则(u,v)为树边
if(!visit[v]) {
children++;
parent[v] = u;
dfs(v);
low
= min(low
, low[v]);
if (low[v] > dfn
) {
printf("bridge: %d %d\n", u, v); // 该边是桥
bridgeCnt++;
}
}
//节点v已访问,则(u,v)为回边
else
if(v != parent
) {
low
= min(low
, dfn[v]);
}
}
if (low
== dfn
)
{
// 因为low
== dfn
,对(parent
,u)来说有dfn
> dfn[ parent
],因此low
> dfn[ parent
]
// 所以(parent
,u)一定是一个桥,那么此时栈内在u之前入栈的点和u被该桥分割开
// 则u和之后入栈的节点属于同一个组
将从u到栈顶所有的元素标记为一个组,并弹出这些元素。
}
}
完整代码:
[cpp]
view plain
copy
#include <iostream>
#include <string.h>
#include <cstdio>
#include <set>
#include <algorithm>
using
namespace std;
#define maxn 20100
#define maxe 200100
struct Edge
{
int v,next;
}E[maxe];
int dfn[maxn],low[maxn],head[maxn],Stack[maxn],Belong[maxn],parent[maxn],counter,len,Stop,n, MinVlaue,m,ans;
void AddEdge(int a, int b)
{
len++;
E[len].v = b;
E[len].next = head[a];
head[a] = len;
}
void dfs(int u)
{
int v;
dfn
= low
=++counter; //初始化dfn与low
Stack[Stop++]=u; //将u加入栈
for (int i = head
; i!=-1; i = E
.next)
{
v = E
.v;
if (!dfn[v]) //节点v未被访问,则(u,v)为树边
{
parent[v]=u;
dfs(v);
low
= min(low
, low[v]);
if(low[v]>dfn
)
{
//printf("bridge: %d %d\n", u, v); // 该边是桥
}
}
//节点v已访问,则(u,v)为回边
else
if(v != parent
)
{
low
= min(low
, dfn[v]);
}
}
if(low
==dfn
)
{
// 因为low
== dfn
,对(parent
,u)来说有dfn
> dfn[ parent
],因此low
> dfn[ parent
]
// 所以(parent
,u)一定是一个桥,那么此时栈内在u之前入栈的点和u被该桥分割开
// 则u和之后入栈的节点属于同一个组
//将从u到栈顶所有的元素标记为一个组,并弹出这些元素。
ans++;
int temp=Stop-1;
while (Stack[temp]!=u)
{
temp--;
}
MinVlaue=*min_element(Stack+temp, Stack+Stop);
do
{
v=Stack[--Stop];
Belong[v]=MinVlaue;
}while (u!=v);
}
}
int main()
{
int a,b;
while (scanf("%d%d", &n, &m)!=EOF)
{
memset(head, -1, sizeof(head));
memset(parent, 0, sizeof(parent));
counter=0;
ans=0;
Stop=0;
memset(dfn,0, sizeof(dfn));
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a, &b);
AddEdge(a,b);
AddEdge(b,a);
}
dfs(1);
printf("%d\n",ans);
for (int i=1; i<=n; i++)
{
printf("%d ",Belong
);
}
}
return 0;
}
作者:
yuchengze
时间:
2016-8-21 12:13
很好的 算法 分享,感谢楼主的分享,路过帮顶
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)
Powered by Discuz! 7.0.0