poj 3177 Redundant Paths 边bcc tarjan

缘起

日常浪费生命. poj 3177 Redundant Paths

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
有F个牧场，1<=F<=5000，现在一个牧群经常需要从一个牧场迁移到另一个牧场。奶牛们已经厌烦老是走同一条路，
所以有必要再新修几条路，这样它们从一个牧场迁移到另一个牧场时总是可以选择至少两条独立的路。现在F个牧场的
任何两个牧场之间已经至少有一条路了，奶牛们需要至少有两条。
给定现有的R条直接连接两个牧场的路，F-1<=R<=10000，计算至少需要新修多少条直接连接两个牧场的路，使得任
何两个牧场之间至少有两条独立的路。两条独立的路是指没有公共边的路，但可以经过同一个中间顶点

【输入】
第一行就是F和R. 然后是R行，为两个正整数，表示2个顶点之间有边连接.

【输出】
最少需要再添加几条边是的达到奶牛的要求

【样例输入】
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

【样例输出】
2

【限制】
1s

此题与 【1】 基本相同. 所以也不说什么了. 就是给你一个无向连通图, 问你最少加几条边之后形成边bcc.

就是跑一次tarjan，然后利用low数组进行缩点. 然后确定缩点后的无向树的叶子数量leaf, 则(leaf+1)>>1 就是答案.

因为本题输入保证了无重边, 正如【1】中所说，我们就可以跑完tarjan算法之后low数组自动帮我们缩好点了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m, timestamp[5005], low[5005], deg[5005], head[5005], cnt,t;
struct Arc
{
	int from, to, nxt;
}g[20005];

void addArc(int a,int b)
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

void dfs(int cur, int fa)
{
	timestamp[cur] = low[cur] = ++t;
	for (int h = head[cur],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!timestamp[to])
		{
			dfs(to, h);
			low[cur] = min(low[cur], low[to]);
		}
		else if ((h>>1)!=(fa>>1)) // 如果h和fa不是同一条边
		{
			low[cur] = min(low[cur], timestamp[to]);
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	memset(head, -1, sizeof(head));
	while(m--)
	{
		int a,b;
		scanf("%d%d", &a, &b);
		addArc(a,b), addArc(b,a);
	}
	dfs(1,-1);
	for (int i = 0,x,y; i<cnt; i+=2) // g的相邻是同一条边,所以是+2
	{
		x = low[g[i].from],y = low[g[i].to];
		if (x!=y) // 如果属于不同的边bcc
		{
			deg[x]++, deg[y]++;
		}
	}
	int ans=  0;
	for (int i = 1; i<=n;i++)
	{
		if (deg[i]==1)
		{
			ans++;
		}
	}
	printf("%d\n",(ans+1)>>1);
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 144kB
Length 1183
Lang C++
Submitted 2019-09-10 19:52:02
Shared
RemoteRunId 20849571

参考

【1】https://yfsyfs.github.io/2019/09/09/poj-3352-Road-Construction-%E8%BE%B9bcc-tarjan/