hdu 4587 TWO NODES

本文从WordPress迁移而来, 查看全部WordPress迁移文章

连通分量

给一个无向图,删除两个点,使得新图的连通分量数最大

做法是枚举一个点,删掉它,然后在剩下的图中求割点

计算删除每个割点,会使每个图分裂为多少部分,枚举割点

(其实也可以不用枚举,只要找到一个割点可以使图分裂成最多部分,那就行了,但枚举的话,时间也差不多)

删除一个点后图的连通分量数为CNT,删除一个割点能产生cnt[u]个连通分量,那么最后的连通分量是CNT + cut[u] - 1

注意,可能在找割点的过程中,找不到一个割点,那么只能随便删除一个点,那么图的连通分量就是 ANS = max(ANS,CNT)吗?

不一定的!因为一个无向图中,如果没有割点,删除一个点,图的连通分量数不一定保持不变,而是可能减少

1
2
3
4
5
例如 
1 2
3 2
4 2
5 2

这种数据,删除点2,后得到1 3 4 5这些连通分量,CNT = 4,这些点中没有一个点是割点,那么任意删除一个点即可

但删除了一个点,连通分量数不变吗?不是的,而是-1

所以为了保证正确性,更新答案应该是

ANS = max(ANS,CNT-1);

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 5010
#define MAX 10010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,tot,head[N];
struct edge{
int u,v,next;
}e[MAX];
int vertex,root,ANS;
int dfn[N],low[N],dcnt;
int cnt[N];
bool vis[N];
vector<int>cp;

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

void tarjan(int u,int fa){
dfn[u] = low[u] = ++dcnt;
vis[u] = true;
int son = 0;
for(int k = head[u]; k != -1; k =e[k].next){
int v = e[k].v;
if(v == fa || v == vertex) continue;
if(!dfn[v]){
son++;
tarjan(v,u);
low[u] = min(low[u],low[v]);
if(u == root && son >= 2) cnt[u]++;
if(u != root && low[v] >= dfn[u]) cnt[u]++;
}
else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(cnt[u]){
cnt[u]++; cp.pb(u);
}
}

void bcc(){
int CNT = 0;
cl(dfn,0); cl(vis,false); cl(cnt,0); cp.clear();
for(int i = 0; i < n; i++)
if(i != vertex && !dfn[i]){
CNT++; root = i;
tarjan(i,-1);
}
if(cp.size() == 0){ //不能写ANS = max(ANS,CNT);
ANS = max(ANS,CNT-1); return ;
}
for(int i = 0; i < cp.size(); i++)
ANS = max(ANS,CNT + cnt[cp[i]] - 1);
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
cl(head,-1); tot = 0;
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
ANS = 1;
for(int i = 0; i < n; i++){
vertex = i;
bcc();
}
printf("%d\n",ANS);
}
return 0;
}