割点，点双连通分量
割点
在无向图上，如果删除某个点（包括所有和它相连的边），图的连通性受到破坏（即分解成多个部分），那么就称删除的这个点为图的割点。
为了求出割点，我们仍然使用\(tarjan\)算法。
考虑 \(low\) 的定义，通常情况下，若一个节点 \(u\) 存在一个儿子 \(v\) ，有
\[
low[v] \ge pre[u]
\]
这代表着，\(v\) 和它的子树被限制在了 \(u\) 及 \(u\) 以下，而不能连接到 \(u\) 以上的任何节点。这样，只要移除节点 \(u\) ，图就会分成至少两个部分：\(u\)和它的祖先兄弟们、\(v\) 和它的孩子们，这样图的连通性就受到了破坏，根据定义 \(u\) 就是割点。
然而，存在一种特殊情况，即 \(u\) 是 \(dfs\) 的起点，并且 \(u\) 只连接着一个点双分量。这时，\(u\) 不是割点。为了防止误判，应在 \(dfs\) 函数结尾对此种情况进行特判。
例题
代码
| #include<iostream>
#include<vector>
using namespace std;
const int N = 2E4 + 10;
int n, m, dt;
int pre[N], low[N];
bool isCut[N];
vector<int> adj[N];
void tarjan(int u, int f){
int child = 0;
low[u] = pre[u] = ++dt;
for(auto v : adj[u]){
if(pre[v] == 0){
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= pre[u]){
isCut[u] = 1;
}
child++;
}
// 因为是无向图，需要排除直接返回父亲的情况，这个判断在有向图的tarjan中并不存在
else if(v != f){
low[u] = min(low[u], pre[v]);
}
}
// 特判 u 是根节点且只有一个真儿子
if(f == 0 && child == 1) isCut[u] = 0;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= n; i++){
if(!pre[i]) tarjan(i, 0);
}
int cnt = 0;
for(int i = 1; i <= n; i++){
if(isCut[i]) cnt++;
}
cout << cnt << endl;
for(int i = 1; i <= n; i++){
if(isCut[i]) cout << i << ' ';
}
cout << endl;
return 0;
}
|
点双连通分量
若一个无向图的一个子图满足其中任意两个不同的节点 \(u\) 和 \(v\) 之间都有至少两条路径（且没有重合的节点）能够相互到达，那么称这个子图为一个点双连通分量（bcc）。
性质：两个不同的点双之间的连接部分一定是割点。
我们在此提供两种方法求得点双分量：
- 标记所有割点，并循环进行 \(dfs\)（不能越过标记的割点）。一次 \(dfs\) 访问到的所有节点就是一个点双分量。
- 仿照
scc 的做法，在遇到每一个节点时将其入栈。当发现节点 \(u\) 的一个儿子 \(v\) 满足 \(low[v]\ge pre[u]\) 时，就把 \(v\) 及以上的节点都划入一个 bcc。
第一种方法需要额外编写一个 dfs 函数，第二种方法可以快速统计每个 bcc 连接了多少个割点，连接了哪些割点，但需要特判根节点。
例题
代码
| #include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N = 1E5 + 10;
int n, m, dt;
int pre[N], low[N], sz[N], ans[N];
vector<int> adj[N];
int tarjan(int u, int f){
long long sum = 0, temp = 1;
sz[u] = 1;
low[u] = pre[u] = ++dt;
for(auto v : adj[u]){
if(v == f) continue;
if(!pre[v]){
sz[u] += tarjan(v, u);
if(low[v] >= pre[u]){
sum += sz[v] * sz[v];
temp += sz[v];
}
low[u] = min(low[u], low[v]);
}
else if(pre[v] < pre[u]){
low[u] = min(low[u], pre[v]);
}
}
// 用 temp 先累加子节点中的点双分量大小总和，再用总体减去自己，以及子节点中的点双，剩下的就是祖先连通块的大小。
temp = n - temp;
// temp 祖先的连通块
// sum 所有儿子连通块的平方和
// 总体减去能相互到达的点的个数
ans[u] = n * n - (temp * temp + sum + 1);
return sz[u];
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
tarjan(1, 0);
for(int i = 1; i <= n; i++){
cout << ans[i] << endl;
}
return 0;
}
|
思路:
为了保证任何一个节点坍塌时，其他节点都能到达一个安全出口，考虑几种情况：
若坍塌的节点是割点，若其连接的一个连通分量还连接着其他分量，那么这个连通分量的节点就可以从另一个割点离开
但是若坍塌的割点是这个连通分量连接的唯一割点，那么这个分量里应该至少有一个安全出口（排除割点）
答案即是叶子节点的数量；每个叶子分量（只连接了一个割点）的非割点节点个数累乘。
技巧: \(Vector\) 数组也可以直接用 \(memset\) 初始化！
易错点:
- 初始化要完整，看好哪些变量和数组要初始化
- 在割点判断中，只有一个儿子的根节点较为特殊，注意是否需要特殊处理
代码
| #include<iostream>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1E3 + 10;
const int M = 505;
int n, m, dt, bccCnt;
int pre[N], low[N], isCut[N], isLeaf[N];
vector<int> adj[N];
vector<int> bcc[N];
stack<int> sta;
void tarjan(int u, int f){
sta.push(u);
low[u] = pre[u] = ++dt;
int child = 0;
for(auto v : adj[u]){
if(v == f) continue;
if(pre[v]){
low[u] = min(low[u], pre[v]);
}
else{
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= pre[u]){
isCut[u] = 1;
bcc[++bccCnt].push_back(u);
int tmp = 1; // u是一个割点
while(sta.top() != v){
bcc[bccCnt].push_back(sta.top());
if(isCut[sta.top()]) tmp++;
sta.pop();
}
bcc[bccCnt].push_back(sta.top());
if(isCut[sta.top()]) tmp++;
sta.pop();
if(tmp == 1) isLeaf[bccCnt] = 1;
}
}
}
// 若根节点只有一个有效儿子
// 在上面的tarjan算法中，这个根节点将会被计算为割点，然而实际上不是，因为它没有父亲(f=0)
// 然而，在上面tarjan内部统计isLeaf时，代码并不知道u不是割点，可能会导致tmp统计的比真实割点数量多一个
// 导致isLeaf被统计为0，故此处需要重新统计。
if(f == 0 && child == 1){
isCut[u] = 0;
int tmp = 0;
for(auto j : bcc[bccCnt]){
if(isCut[j]) tmp++;
}
if(tmp == 1) isLeaf[bccCnt] = 1;
}
}
int main(){
int CaseNum = 0;
while(1){
// for(int i = 1; i < N; i++){
// bcc[i].clear();
// }
// 注意，Vector也可以直接用memset初始化
memset(bcc, 0, sizeof(bcc));
memset(adj, 0, sizeof(adj));
memset(isCut, 0, sizeof(isCut));
memset(pre, 0, sizeof(pre));
memset(low, 0, sizeof(low));
memset(isLeaf, 0, sizeof(isLeaf));
dt = 0;
bccCnt = 0;
cin >> m;
if(m == 0) break;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
tarjan(1, 0);
cout << "Case " << ++CaseNum << ": ";
if(bccCnt == 1){
cout << "2 ";
cout << bcc[1].size() * (bcc[1].size() - 1) / 2 << endl;
continue;
}
long long leafCnt = 0, sum = 1;
for(int i = 1; i <= bccCnt; i++){
if(isLeaf[i]){
leafCnt++;
if(bcc[i].size() != 1) sum *= bcc[i].size() - 1;
else sum *= 1; // 可注释
}
}
cout << leafCnt << ' ' << sum << endl;
}
return 0;
}
|