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;
}