当前位置: 代码迷 >> 综合 >> POJ 3352 Road Construction 点双连通分支 -
  详细解决方案

POJ 3352 Road Construction 点双连通分支 -

热度:135   发布时间:2023-09-23 07:46:30.0

题目地址:http://poj.org/problem?id=3352

题意:给你一个图,要求你加入最少的边,使得最后得到的图为一个边双连通分支。所谓的边双连通分支,即不存在桥的连通分支。


思路:

可以求出所有的桥,把桥删掉。然后把所有的连通分支求出来,显然这些连通分支就是原图中的双连通分支。把它们缩成点,然后添上刚才删去的桥,就构成了一棵树。在树上添边使得树变成一个双连通分支即可。


本题只要求输出一共需要添加多少条边,而不需要求具体的方案。其实可以统计度为1的叶子节点(共有x个),然后直接输出(x+1)/2即可


#include<iostream>
#include<cstdio>
#include<vector>
#include<stack> 
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
typedef pair<int,int> Edge; 
int index=0,ncolor;  
vector<bool> vis(maxn);    
vector<int> dfn(maxn),low(maxn),st,ID(maxn);
vector<vector<int> > G(maxn),color(maxn);  
vector<Edge> bridge;
void Tarjan(int u,int father) 
{dfn[u]=low[u]=++index;vis[u]=true;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!vis[v]){Tarjan(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v])  bridge.push_back(Edge(u,v));}else if(father!=v) //只能由非父子边更新 low[u]=min(low[u],dfn[v]);}
}
void Tarjan2(int u)  //染色 
{dfn[u]=low[u]=++index;vis[u]=true;st.push_back(u);for(int i=0;i<G[u].size();i++){int v=G[u][i];if(!vis[v]){Tarjan2(v);low[u]=min(low[u],low[v]);}else if(find(st.begin(),st.end(),v)!=st.end()) //in stacklow[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){int v; ncolor++;do{v=st.back(); st.pop_back();color[ncolor].push_back(v);ID[v]=ncolor;}while(v!=u);}
}
void getGraph(int n){index=ncolor=0;fill(vis.begin(),vis.begin()+n+1,false);for(int i=1;i<=n;i++)if(!vis[i]) Tarjan2(i);
} 
int solve(int n)
{int m=0,ans; //m标记出度为1的点有几个 vector<int> points;for(int i=1;i<=ncolor;i++) {points.clear();for(int j=0;j<color[i].size()&&points.size()<=1;j++){int u=color[i][j];for(int k=0;k<G[u].size()&&points.size()<=1;k++){int v=G[u][k];if(ID[u]!=ID[v]&&find(points.begin(),points.end(),v)==points.end())  //有出度 points.push_back(v);}}if(points.size()==1) m++;}return m;
}
int main()
{int n,m;cin>>n>>m;while(m--){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}index=0;Tarjan(1,0);  for(int i=0;i<bridge.size();i++){  //删去 int u=bridge[i].first,v=bridge[i].second;for(int j=0;j<G[u].size();j++){if(G[u][j]==v) G[u].erase(G[u].begin()+j);}for(int j=0;j<G[v].size();j++){if(G[v][j]==u) G[v].erase(G[v].begin()+j);}}getGraph(n);  //染色 ,缩点 for(int i=0;i<bridge.size();i++){  //加上桥边 G[bridge[i].first].push_back(bridge[i].second);G[bridge[i].second].push_back(bridge[i].first);}cout<<(solve(n)+1)/2<<endl;return 0;
} 


  相关解决方案