2023大二上第十一周随笔
前面几周浅浅练了一下最小生成树和二分图的题（最小生成树还有好几题没写，好难，回头再补）。连通性问题这块我还是一点没学过。所以这周还是先看看连通性问题这块知识。
2023-11-10（周五）
这个星期比较懒，前面都没怎么学。今天才开始。
今天看的资料:双连通分量 - OI Wiki (oi-wiki.org),割点和桥 - OI Wiki (oi-wiki.org)
学习的内容是用Tarjan算法求图中的割点和边。
算法中dfn数组其实就是存的每个数再dfs序中的出现位置，low数组用它来存储不经过其父亲能到达的最小的时间戳。
结论也很简单 节点u是节点v的父节点
1.LOWv>=DFNu则u是割点。
- LOWv>DFNu则节点u和节点v之间的点为桥。
其实没太理解为什么。
60 分钟搞定图论中的 Tarjan 算法（一） - 知乎 (zhihu.com)这篇文章讲的更清楚一点（wiki上的教程还是一如既往的抽象）
看完之后大概懂了。
LOWv>=DFNu其实就是要想访问节点v都必然会先访问节点u（u会比v先被访问），所以就是想要访问节点v绕不开节点u，u就是割点
理解之后主要难点就在怎么求回溯数组low
借用wiki上的代码
下面代码实现了求割边，其中，当 isbridge[x] 为真时，(father[x],x) 为一条割边。
int low[MAXN], dfn[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];
void tarjan(int u, int fa) { //求以节点u为根节点的树
father[u] = fa; //记录u的父节点fa
low[u] = dfn[u] = ++dfs_clock; //记录u在dfs序上的时间挫
for (int i = 0; i < G[u].size(); i++) { //遍历u的子节点
int v = G[u][i]; //v是u的子节点
if (!dfn[v]) {//如果v没有被访问过
tarjan(v, u); //求以节点v为根节点的搜索树
low[u] = min(low[u], low[v]); //v是以u为根节点的树上的结点
if (low[v] > dfn[u]) {
isbridge[v] = true;
++cnt_bridge;
}
} else if (dfn[v] < dfn[u] && v != fa) { //v比u先被访问，v不是u的父节点，说明边u-v不是搜索树上的边
low[u] = min(low[u], dfn[v]);
}
}
}
写几道例题
1.P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
炸铁路
题目描述
A 国派出将军 uim，对 B 国进行战略性措施，以解救涂炭的生灵。
B 国有 $n$ 个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。
uim 发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为 key road。
uim 为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。
然而，只有一发炮弹（A 国国会不给钱了）。所以，他能轰炸哪一条铁路呢？
输入格式
第一行 $n,m\ (1 \leq n\leq 150$，$1 \leq m \leq 5000)$，分别表示有 $n$ 个城市，总共 $m$ 条铁路。
以下 $m$ 行，每行两个整数 $a, b$，表示城市 $a$ 和城市 $b$ 之间有铁路直接连接。
输出格式
输出有若干行。
每行包含两个数字 $a,b$，其中 $a<b$，表示 $\lang a,b\rang$ 是 key road。
请注意：输出时，所有的数对 $\lang a,b\rang$ 必须按照 $a$ 从小到大排序输出；如果$a$ 相同，则根据 $b$ 从小到大排序。
样例 #1
样例输入 #1
6 6 1 2 2 3 2 4 3 5 4 5 5 6样例输出 #1
1 2 5 6
AC代码:
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int MAXN = 1010;
int low[MAXN], dfn[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];
void tarjan(int u, int fa) {
father[u]=fa;
low[u]=dfn[u]=++dfs_clock;
for(auto v:G[u]){
if(!dfn[v]){
tarjan(v, u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
isbridge[v]=true;
++cnt_bridge;
}
}else if(v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
}
int cmp(pair<int,int> a , pair<int,int> b){
if(a.first==b.first) return a.second<b.second;
return a.first<b.first;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
tarjan(1,0);
vector<pair<int,int>>path;
set<pair<int,int>> ppp;
for(int i=1;i<=n;i++){
if(!isbridge[i]) continue;
int a=i;
int b=father[i];
if(a>b) swap(a,b);
if(ppp.find({a,b})!=ppp.end()) continue;
ppp.insert({a,b});
path.push_back({a,b});
}
sort(path.begin(),path.end(),cmp);
for(auto [x,y]:path) cout<<x<<" "<<y<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
P3388 【模板】割点（割顶） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
【模板】割点（割顶）
题目背景
割点
题目描述
给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。
输入格式
第一行输入两个正整数 $n,m$。
下面 $m$ 行每行输入两个正整数 $x,y$ 表示 $x$ 到 $y$ 有一条边。
输出格式
第一行输出割点个数。
第二行按照节点编号从小到大输出节点，用空格隔开。
样例 #1
样例输入 #1
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6样例输出 #1
1 5提示
对于全部数据，$1\leq n \le 2\times 10^4$，$1\leq m \le 1 \times 10^5$。
点的编号均大于 $0$ 小于等于 $n$。
tarjan图不一定联通。
脑子不好使了，改半天
AC代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n';
using namespace std;
const int MAXN = 1e5 + 10;
int low[MAXN], dfn[MAXN], dfs_clock;
vector<int> G[MAXN];
bool flag[MAXN];
int res=0;
void tarjan(int u, int fa){
low[u] = dfn[u] = ++dfs_clock;
int child=0;
for(auto v:G[u]){
if(!dfn[v]){
child++;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v]>=dfn[u]&&u!=fa&&!flag[u]){
flag[u]=true;
res++;
}
}else if(v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
if(fa==u&&child>=2&&!flag[u]){
flag[u]=true;
res++;
}
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!dfn[i]){
dfs_clock=0;
tarjan(i,i);
}
cout<<res<<endl;
for(int i=1;i<=n;i++)
if(flag[i]) cout<<i<<" ";
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
//cin>>T;
while(T--)solve();
return 0;
}
求割点比求桥要多判断一些东西。为顶点的状态要单独拿出来判断。而且这道题可能不是联通图，所以要每个点都判断一些访问过没有，没有访问过就继续以这个点为顶点调用函数。
好像学会了，但是写起来肯定还是要翻板子。