POJ 3177 Redundant Paths （tarjan边双连通分量）

题目大意是给定一些牧场，牧场和牧场之间可能存在道路相连，要求从一个牧场到另一个牧场要有至少两条以上不同的路径，且路径的每条path是分立的独立的，意为不能有公共道路，问最少添加多少条道路达成题目的要求。

图论问题，因为题目要求不能有公共道路，就是路径不能有公共边。题目转化为求图的边双连通分量，每个边双连通分量内各个牧场肯定存在不同路径可以相互到达，所以要求出图内有多少个边双连通分量，缩点后添边去满足题意。最终缩点后的图为树，所以最简单的办法就是连接树的叶子节点，答案即为树的（叶子节点个数+1）/2。因为是无向图，所以缩点后找到度为1的节点即为叶子节点。

建双向图，直接跑tarjan求BCC，在求BCC的时候注意是遍历边，而非节点。

#include<iostream>

#include<stack>

#include<vector>

#include<algorithm>

#include<cstring>

using namespace std;

struct node{

	vector<int> vex;

	vector<int> num;

};

struct edge{

	int a,b,id,cut;

}E[5005*2];//a为边的起点，b为边的终点，id为边的输入目录 

node g[5005];

int newnode[5005];

int bccnum = 0;

int tot;

int visit[5005],dfn[5005],low[5005];

stack<int> stk;

void tarjan(int x,int fa){

	dfn[x] = low[x] = ++tot;

	stk.push(x);//节点入栈

	for(int i = 0;i<g[x].vex.size() ;i++){

		int tedge = g[x].num[i]; //边序号，后续可以由边序号作为索引找到该边的id（目录） 

		if(visit[tedge]){

			continue;

		}

		visit[tedge] = visit[tedge^1] = 1;//标记双向边已经访问过

		if(!dfn[g[x].vex[i]]){

			tarjan(g[x].vex[i],x);

			low[x] = min(low[x],low[g[x].vex[i]]);

			if(low[g[x].vex[i]] > dfn[x] ){

				E[tedge].cut = E[tedge^1].cut = 1;//该tedge边为割边，做标记

			}

		}

		else

			low[x] = min(low[x],dfn[g[x].vex[i]]);

	}

	if(dfn[x] == low[x]){

		bccnum++;

		//找到一个BCC，依次把这个BCC的节点出栈，并做缩点操作

		int v;

        do

        {

            v = stk.top() ;

            //visit[v] = 0;

            stk.pop();

            newnode[v] = bccnum;// v节点所属‘bccnum’的边双连通分量

        }while(v != x);

	}

}

int edgenum = 0;//边的序号从0开始，因为是建立双向边所以两条边标记的序号是异或关系，由边序号可以找到该边的id

void addedge(int u,int v,int id){

	E[edgenum].a = u;

	E[edgenum].b = v;

	g[u].num.push_back(edgenum);

	E[edgenum++].id = id;

}

int main(){

	int F,R;

	cin>>F>>R;

	for(int i = 1;i<=R;i++){

		int u,v;

		cin>>u>>v;

		addedge(u,v,i);

		addedge(v,u,i);

		g[u].vex.push_back(v);

		g[v].vex.push_back(u);

	}

	for(int i = 1;i<=F;i++){

		if(!dfn[i]){

			tarjan(i,0);

		}

	}

	node newG[bccnum+1];

	//cout<<bccnum<<endl;

	int mark[bccnum+1];

	memset(mark,0,sizeof(mark));

	for(int i = 1;i<=F;i++){

		for(int j = 0;j<g[i].vex.size() ;j++ ){

			if(E[g[i].num[j]].cut ){ //找到了一个割边

				mark[newnode[g[i].vex[j]]] ++;//缩点后该BCC的度++

			}

		}

	}

	int ans = 0;

	for(int i = 1;i<=bccnum;i++){

		if(mark[i] == 1){//缩点后度为1的BCC进行统计

			//cout<<"x";

			ans++;

		}

	}

	cout<<(ans+1)/2;

	return 0;

}

巴特西

POJ 3177 Redundant Paths （tarjan边双连通分量）

最新文章

热门文章