当前位置: 代码迷 >> 综合 >> HDU3394 Railway(点双连通分量)
  详细解决方案

HDU3394 Railway(点双连通分量)

热度:18   发布时间:2024-01-16 13:29:21.0

题意:

给出一个无向图,求出它的冲突边数和多余边数,冲突边就是那些同时存在于多个环中的边,而多余边是不在任何一个环中的边.。

要点:

多余边很明显就是桥,我们可以推断除冲突边只能在点双连通分量中,感觉边双应该也行,主要就是求出分量后看分量中点数n和边数m的关系,如果n<m,整个分量中所有的边都是冲突边,因为总是一个大环分成几个内部小环,大环跟内部小环肯定冲突。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn = 10000 + 10;
vector<int> g[maxn], bcc[maxn];
int dfs_clock, bcc_cnt,n,m,ans1,ans2;
int pre[maxn], bccno[maxn];
typedef pair<int, int> Pair;
stack<Pair> s;void solve()//冲突边计算
{for (int u = 1; u <= bcc_cnt; u++){int sum = 0;bool vis[maxn];memset(vis, false, sizeof(vis));for (int i = 0; i < bcc[u].size(); i++)vis[bcc[u][i]] = true;for (int i = 0; i < bcc[u].size(); i++){int x