HDU3394 Railway

http://acm.hdu.edu.cn/showproblem.php?pid=3394
题意：
有一个公园有n个景点，这n个景点由m条无向道路连接而成。
公园的管理员准备规划一一些形成回路的参观路线(参观路线不能经过同一个景点，是一个简单环)。如果一条道路被多条参观路线公用，那么这条路是冲突的；如果一条道路没在任何一个回路内，那么这条路是多余的道路。
问分别有多少条有冲突的路和多余的路。

思路：多余的路就是桥，因为割掉就图不连通了。
冲突的路比较难想，画图，得知判定条件是：边数多于点数的点双的每一条边都是。

#include
using namespace std;
const int maxn=10000+100;
typedef pair<int,int> P;int n,m,dfs_clock,bridge,iscut[maxn],pre[maxn],bccno[maxn],bcc_cnt,cnt[maxn],ans;
vector<int> G[maxn],bcc[maxn];
stack<P> s;int dfs(int u,int fa)
{int lowu=pre[u]=++dfs_clock;int child=0;for(int i=0;i<G[u].size();i++){   int v=G[u][i];P e=make_pair(u,v);if(!pre[v]){   s.push(e);child++;int lowv=dfs(v,u);lowu=min(lowu,lowv);if(lowv>pre[u])bridge++;if(lowv>=pre[u]){iscut[u]=true;bcc_cnt++;bcc[bcc_cnt].clear();for(;;){P x=s.top();s.pop();cnt[bcc_cnt]++;if(bccno[x.first]!=bcc_cnt){bcc[bcc_cnt].push_back(x.first);bccno[x.first]=bcc_cnt;}if(bccno[x.second]!=bcc_cnt){bcc[bcc_cnt].push_back(x.second);bccno[x.second]=bcc_cnt;}if(x.first==u && x.second==v)break;}}}else if(pre[v]<pre[u] && v!=fa){s.push(e);lowu=min(lowu,pre[v]);}}if(fa<0 && child==1)iscut[u]=0;return lowu;
}void find_bcc()
{memset(pre,0,sizeof(pre));memset(iscut,0,sizeof(pre));memset(bccno,0,sizeof(pre));memset(cnt,0,sizeof(pre));while(s.empty()==0)s.pop();ans=bridge=dfs_clock=bcc_cnt=0;for(int i=1;i<=n;i++)if(!pre[i])dfs(i,-1);for(int i=1;i<=bcc_cnt;i++)if(cnt[i]>bcc[i].size())ans+=cnt[i];printf("%d %d\n",bridge,ans);
}int main()
{//freopen("input.in","r",stdin);while(cin>>n>>m && n){int a,b;for(int i=1;i<=n;i++)G[i].clear();while(m--){scanf("%d%d",&a,&b);a++;b++;G[a].push_back(b);G[b].push_back(a);}find_bcc();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！