Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 11184 Accepted Submission(s): 2573
文章目录
Problem Description
N planets are connected by M bidirectional channels that allow
instant transportation. It’s always possible to travel between any two
planets through these channels. If we can isolate some planets from
others by breaking only one channel , the channel is called a bridge
of the transportation system. People don’t like to be isolated. So
they ask what’s the minimal number of bridges they can have if they
decide to build a new channel. Note that there could be more than
one channel between two planets.
Input
The input contains multiple cases. Each case starts with two
positive integers N and M , indicating the number of planets and the
number of channels. (2<=N<=200000, 1<=M<=1000000) Next M lines
each contains two positive integers A and B, indicating a channel
between planet A and B in the system. Planets are numbered by 1…N.
A line with two integers ‘0’ terminates the input.
Output
For each case, output the minimal number of bridges after building a
new channel in a line.
Sample Input
4 4
1 2
1 3
1 4
2 3
0 0
Sample Output
0
题意：
n个点，m个边，问在添加一个边后，输出最小数量的桥
（桥：如果去掉这个边，会使得一些点与其他点隔离）
题解：
tarjan求出每个边双连通分量后，对每个双连通分量进行缩点，缩点就就是一颗无根树，在树上添加一个边，使得树上的桥最少，该怎么做？
一个树，所有边都是桥（因为你去掉任何一个边都会使得点与点分离），而我们只能加一个边，那我们就尽可能保留最多点，这样就可以最大程度减少桥的数量，最多能减少多少？其实就是树上的最长路，也就是从一个叶子节点到另外一个叶子节点，连接后，这个就形成闭环，因为是最长路，所有保留的最多。问题就转变成求树上最长路，即求树的直径
求树的直径可以用两边dfs来实现（原理我也忘了）
从任意一点x开始，dfs找与x最远的点y，然后从y开始找与y最远的点z，x与z的距离就是
代码：
代码参考
本人对代码详细注释
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const double EPS = 1e-8;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 2e5+10;
struct Edge
{
int to, next;
}edge[MAXN*10];
int tot, head[MAXN];
vector<int>g[MAXN];
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int index, dfn[MAXN], low[MAXN];
int top, Stack[MAXN], instack[MAXN];
int block, belong[MAXN];
void Tarjan(int u, int pre)
{
dfn[u] = low[u] = ++index;
Stack[top++] = u;
instack[u] = true;
for(int i = head[u]; i!=-1; i = edge[i].next)
{
//因为一对点之间可能有多条边，所以不能根据v是否为上一个点来防止边是否被重复访问。而需要根据边的编号
if((i^1)==pre) continue;
int v = edge[i].to;
if(!dfn[v])
{
Tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else if(instack[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u]==dfn[u])
{
block++;
int v;
do
{
v = Stack[--top];
instack[v] = false;
belong[v] = block;
}while(v!=u);
}
}//常规的tarjan缩点操作
int diameter, endpoint;
int dfs(int u, int pre, int dep)//当前节点 前节点 深度
{
if(dep>diameter)//深度越深时，长度越长
{
endpoint = u; //记录第一个端点
diameter = dep; //最深深度
}
for(int i = 0; i<g[u].size(); i++)
if(g[u][i]!=pre)
dfs(g[u][i], u, dep+1);
}
void init(int n)
{
tot = 0;
memset(head, -1, sizeof(head));
index = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
top = 0;
memset(instack, false, sizeof(instack));
block = 0;
for(int i = 1; i<=n; i++)
belong[i] = i, g[i].clear();
}
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) && (n||m) )
{
init(n);
for(int i = 1; i<=m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
Tarjan(1, -1);
for(int u = 1; u<=n; u++)
for(int i = head[u]; i!=-1; i = edge[i].next)
{
int v = edge[i].to;
if(belong[u]!=belong[v])//如果不在同一个强连通量
g[belong[u]].push_back(belong[v]);//生成树
}
endpoint = 1, diameter = 0;
dfs(1, -1, 0);
dfs(endpoint, -1, 0);
printf("%d\n", block-1-diameter);
//block（分块数量）-1表示最初桥的数量
//diameter表示最长距离，也就是取消的桥数量
}
}
京公网安备 11010502036488号