HDU3394 Railway（Tarjan求桥和点双连通分量）

Railway

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3467
Accepted Submission(s): 1159

Problem Description

There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.

Input

The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.

Output

Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.

Sample Input

Sample Output

1 5

Source

The 5th Guangting Cup Central China Invitational Programming Contest

链接

http://acm.hdu.edu.cn/showproblem.php?pid=3394

题意

给一个无向图。如果至少有两个环共用了一些边，那么这些边被认为是“冲突边”。如果一些边不在任何一个环中，这些边被认为是“多余边”。分别输出图中“多余边”和“冲突边”的数量。

题解

“多余边”不在任何一个环中，那么多余边一定是桥，所以统计这个无向图中有多少桥即可。
“冲突边”有多少，这个有点费劲，但是不难想到。如果一个环比较特殊，n个点刚好n条边，例如(1, 2)、(1, 3)、(2, 3)这种环，这个环内，一条“冲突边”都没有，但是如果一个环内的边数大于点数，那么这个环内所有边都是“冲突边”（真可惜，因为有多出来的那些边后，相当于把最外面的大环分割成了内部的几个小环，这些小环和小环之间，小环和大环之间一定会公用一些边，这些边就是“冲突边”，而且可以发现，所有边都会被公用，太可惜了......），例如sample里面的(5,6)(5,4)(6,7)(4,7)(5,7)，相当于最外面的大环<6,5,4,7,6> ，而里面的边(5,7)把这个大环分割成了两个小环。因为是求环,所以求的是点双连通分量。所以做法就是，求出这个无向图有多少个点双连通分量，对于每个点双连通分量，如果内部的边数>点数，那么这些边全部都是冲突边。

参考了Gitfan的题解。

代码

Status	Accepted
Time	358ms
Memory	8608kB
Length	3164

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 10010;
const int maxm = 200010;
int n, m, tot, cnt, bcc_cnt, bridges; // 连通分量数量和桥数量
int head[maxn], dfn[maxn], low[maxn], bccno[maxn], iscut[maxn]; // 连通分量编号和割点标记

struct Node
{
   int to, next, cut;
}edge[maxm];

void addedge(int u, int v) // 链式前向星存图
{
   edge[cnt].cut = 0;
   edge[cnt].to = v;
   edge[cnt].next = head[u];
   head[u] = cnt++;
}

struct Edge // 边
{
   int u, v;
   Edge(){}
   Edge(int u, int v):u(u), v(v){}
};

stack <Edge> S; // 栈中保存连通分量的边
vector<int>bcc[maxn]; // 连通分量中的点
vector<Edge>edgecnt[maxn]; // 连通分量重的边数

void init() // 初始化
{
   bcc_cnt = tot = cnt = bridges = 0;
   for (int i = 0; i <= n; ++i)
   {
       head[i] = -1;
       dfn[i] = low[i] = bccno[i] = iscut[i] = 0;
       bcc[i].clear();
       edgecnt[i].clear();
   }
   memset(edge, 0, sizeof(edge));
}

void tarjan(int u, int father) // tarjan求连通分量
{
   low[u] = dfn[u] = ++tot;
   int child = 0;
   bool flag = true;
   for (int i = head[u]; i != -1; i = edge[i].next)
   {
       int v = edge[i].to;
       if (flag && v == father) // 处理可能存在的重边
       {
           flag = false;
           continue;
       }
       Edge e(u, v);
       if (!dfn[v])
       {
           S.push(e);
           child++;
           tarjan(v, u);
           low[u] = min(low[u], low[v]);
           if (low[v] >= dfn[u]) // 割顶
           {
               iscut[u] = true;
               bcc_cnt++;
               while (1) // 取出栈中连通分量
               {
                   Edge tmp = S.top();
                   S.pop();
                   edgecnt[bcc_cnt].push_back(tmp);
                   // 防止重复加点
                   if (bccno[tmp.u] != bcc_cnt)
                   {
                       bcc[bcc_cnt].push_back(tmp.u);
                       bccno[tmp.u] = bcc_cnt;
                   }
                   if (bccno[tmp.v] != bcc_cnt)
                   {
                       bcc[bcc_cnt].push_back(tmp.v);
                       bccno[tmp.v] = bcc_cnt;
                   }
                   if (tmp.u == u && tmp.v == v)
                       break;
               }
           }
           if (low[v] > dfn[u]) // 桥
           {
               edge[i].cut = 1;
               edge[i+1].cut = 1;
               bridges++;
           }
       }
       else if (dfn[v] < dfn[u]) // 用反向边进行更新
       {
           S.push(e);
           low[u] = min(low[u], dfn[v]);
       }
   }
   if (father < 0 && child == 1)
       iscut[u] = 0;
}

void solve()
{
   for (int i = 1; i <= n; ++i) // 图可能不连通
   {
       if (!dfn[i])
           tarjan(i, -1);
   }
   int edges = 0;
   for (int i = 1; i <= bcc_cnt; ++i) 
   {
       if (edgecnt[i].size() > bcc[i].size()) // 判断连通分量中的点数与边数
           edges += edgecnt[i].size();
   }
   printf("%d %d\n", bridges, edges);
}

int main()
{
   while (scanf("%d%d", &n, &m) == 2)
   {
       if (n == 0 && m == 0)
           break;
       init();
       int u, v;
       for (int i = 0; i < m; ++i)
       {
           scanf("%d%d", &u, &v);
           u++, v++;
           addedge(u, v);
           addedge(v, u);
       }
       solve();
   }
   return 0;
}

对求无向图的点双连通分量还是不太熟悉，不过图的连通性问题算是到此结束了。

The end.
2018-07-18 星期三