Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

poj 1523 关节点

来源: 未知 分享至:

本题求关节点的算法与求桥的算法基本相似,只不过在其中加了一个常量时间的测试,那么说一下关节点的判断条件:有两个双连通分量AB,通过关节点x相连,那么分别处于两个双连通分量的ab顶点,连接他们的任何路径都必须通过x,那么单考虑B,以x为根B形成的搜索子树中的任何顶点的孩子都不会越过x顶点,也就是说pre[x]<=low[b](pre[],low[]下有说明)总会成立。

这道题需要注意的就是找的每一个关节点确定其双连通分量时,因为自身所在部分也是一个双连通分量所以输出时要加一。还有一点就是搜索树的根有两棵或两棵以上的子树时才是一个关节点,所以在确定其连通分量时要减一。

代码如下:

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct leaves
{
	int node;
	int network;
}part[1001];
vector <int> map[1001];
int cnt,length,pre[1001],low[1001];
int search(int s,int t)
{
	int i;
	for(i=0;i<map[s].size();i++)
		if(map[s][i]==t) return 0;
	return 1;
}
int cmp(const void* a,const void* b)
{
	if(((leaves*)a)->node>((leaves*)b)->node)
		return 1;
	return 0;
}
int dfs(int root,int parent)
{
	int i,k,count=0;
	pre[root]=++cnt; //搜索序号
	low[root]=pre[root];//low[]记录从每个顶点通过一系列树边跟一条回边可达到的最小搜索序号
	for(i=0;i<map[root].size();i++)
	{
		k=map[root][i];
		if(pre[k]==-1)
		{
			dfs(k,root);
			if(low[root]>low[k]) low[root]=low[k];//回溯更新最小搜索序号
			if(pre[root]<=low[k]) count++;//满足该条件确定一个关节点
		}
		else if(k!=parent && low[root]>pre[k])//遇到回边确定最小搜索序号
			low[root]=pre[k];
	}
    if(count)
	{
		leaves e={root,count};
		part[length++]=e;
	}
	return 0;
}
int print(int count)
{
	int i;
    if(--part[length-1].network==0) length--;//确定根是不是关节点
    qsort(part,length,sizeof(part[0]),cmp);
	cout<<"Network #"<<count<<endl;
	for(i=0;i<length;i++)
		cout<<"  SPF node "<<part[i].node<<" leaves "<<part[i].network+1<<" subnets"<<endl;
	if(i==0)
		cout<<"  No SPF nodes"<<endl;
	cout<<endl;
	return 0;
}
int main()
{
	int i,s,t,count=0;
	while(cin>>s && s && cin>>t)
	{
		count++;
		if(search(s,t))
		{
			map[s].push_back(t);
			map[t].push_back(s);
		}
		while(cin>>s && s &&cin>>t)
			if(search(s,t))
			{
				map[s].push_back(t);
				map[t].push_back(s);
			}
		length=cnt=0;
		memset(part,0,sizeof(part));
		for(i=1;i<1001;i++) pre[i]=-1;
		dfs(1,0);	
		print(count);
		for(i=0;i<1001;i++)
			map[i].clear();
	}
	return 0;
}


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史