Znzryb's Blog
0%

P2860 [USACO06JAN] Redundant Paths G（打印）

Posted on Edited on

思路讲解

image

low值相同的点我们可以进行缩点，看成是一个点。

如何求low值及其定义见

为什么可以这样统计缩点的入度，不会有两个low值相同的点与该点相连嘛？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll tarjan(){
	for(int i=1;i<=N;++i){
		for(int j=0;j<g[i].size();++j){
			ll node=g[i][j];
			if(low[node]!=low[i]){
				degree[low[i]]+=1;  // 以该low值为代表的缩点入度+1
			}
		}
	}
	ll res=0;
	for(int i=1;i<=N;++i){
		if(degree[i]==1){
			++res;
		}
	}
	return ceil(res*1.0/2);
}

显然不可能，有两个low值相同的点与该点相连，那么该点必然与这些点都有共同的low值

image

AC代码

AC

https://www.luogu.com.cn/record/198957305

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=5010;
vector<ll> g[MAXN];

ll N,M;
pll edge[10010];
// 该点的dfs序  子孙可以达到的dfsn值最小的点的dfsn
ll dfsn[MAXN],low[MAXN];
// dfs序编号（时间戳）
ll idx=0;
bool vis[MAXN];
// 计算每个缩点的入度
ll degree[MAXN];
ll dfs(int x,int pa){
	vis[x]=true;
	dfsn[x]=++idx;
	low[x]=dfsn[x];	// 暂设low[x]为自己的dfsn序
	for(int i=0;i<g[x].size();++i){
		if(!vis[g[x][i]]){
			low[x]=min(dfs(g[x][i],x),low[x]);
		}else if(g[x][i] != pa ){
			// 不是父节点且被访问过的要搞一下
			low[x]=min(dfsn[g[x][i]],low[x]);
		}else if(g[x][i+1]==pa){
			low[x]=min(dfsn[g[x][i]],low[x]);
		}
	}
	return low[x];
}
ll tarjan(){
	for(int i=1;i<=N;++i){
		for(int j=0;j<g[i].size();++j){
			ll node=g[i][j];
			if(low[node]!=low[i]){
				degree[low[i]]+=1;
			}
		}
	}
	ll res=0;
	for(int i=1;i<=N;++i){
		if(degree[i]==1){
			++res;
		}
	}
	return ceil(res*1.0/2);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;++i){
		cin>>edge[i].first>>edge[i].second;
		if(edge[i].first>edge[i].second)
			swap(edge[i].first, edge[i].second);
	}
	sort(&edge[1], &edge[M+1]);
	for(int i=1;i<=M;++i){
		g[edge[i].first].push_back(edge[i].second);
		g[edge[i].second].push_back(edge[i].first);
	}
	// which are numbered 1..F 一定有点1且图联通
	// They currently have at least one route between each pair of fields and want to have at least two. 
	dfs(1,1);
	cout<<tarjan()<<'\n';
	return 0;
}
/*
WA 63pts https://www.luogu.com.cn/record/198897988
AC https://www.luogu.com.cn/record/198957305
*/

心路历程（WA，TLE，MLE……）

题解讲的云里雾里的，有的时候还是得看书，黑书牛逼！