题目:求一个图删除一个点之后,联通块最多有多少。
题面:给定一个无向图的顶点数n和边数m,以及边的连接关系。删除一个顶点后,求联通块的最大数量。
思路:删去了一个点之后,多的连通块个数相当于它的子树个数(就是dfn没更新过的那些点,不包括dfn更新过的点)。根节点增加的是子树个数减一,不然你会WA。因此在Tarjin的大框架下没有什么要大改的地方。下面是代码:
```c
void tarjin(int k) {
dfn[k] = low[k] = ++tot;
int cntt = 0;
for (int i = head[k]; i; i = a[i].nxt) {
if (!dfn[a[i].to]) {
tarjin(a[i].to), cntt++, low[k] = min(low[k], low[a[i].to]);
if (low[a[i].to] >= dfn[k] && k != rt) f[k]++;
} else low[k] = min(low[k], dfn[a[i].to]);
}
if (k == rt) f[k] = cntt - 1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int ansn = 0;
for (int i = 1; i <= n; i++) {
if (!dfn[i]) rt = i, tarjin(i), ansn++;
}
int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
printf("%d
", ans + ansn);
return 0;
}
```
```cpp
#include
using namespace std;
int n, m, x, y, f[10005], ansn, ans;
int head[10005], cnt, rt;
int dfn[10005], low[10005], tot;
struct node {
int nxt, to;
} a[1000005];
void add(int x, int y) {
a[++cnt].to = y, a[cnt].nxt = head[x], head[x] = cnt;
}
void tarjin(int k) {
dfn[k] = low[k] = ++tot;
int cntt = 0;
for (int i = head[k]; i; i = a[i].nxt)
if (!dfn[a[i].to]) {
tarjin(a[i].to), cntt++, low[k] = min(low[k], low[a[i].to]);
if (low[a[i].to] >= dfn[k] && k != rt) f[k]++;
} else low[k] = min(low[k], dfn[a[i].to]);
if (k == rt) f[k] = cntt - 1;
}
int main() {
scanf("%d%d", &n, &m);
while (n != 0) {
memset(f, 0, sizeof(f)), memset(dfn, 0, sizeof(dfn)), memset(low, 0, sizeof(low));
memset(head, 0, sizeof(head)), cnt = ansn = tot = 0, ans = -2;
for (int i = 1; i <= m; i++) scanf("%d%d", &x, &y), ++x, ++y, add(x, y), add(y, x);
for (int i = 1; i <= n; i++) if (!dfn[i]) rt = i, tarjin(i), ansn++;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
printf("%d\n", ans + ansn), scanf("%d%d", &n, &m);
}
return 0;
}
```
小结:
这个系列的题目都是以tarjin为基础进行一些改动,关键在于思路和熟练掌握模板。如果你有任何不明白的地方,请随时私信我。现在就让我们结束这篇内容,撒花庆祝吧!别忘了点赞、关注,谢谢大家的支持!