526互联

2023大二上第十一周记录

发布时间 2023-12-04 21:22:38作者: zfxyyy

2023大二上第十一周随笔

1

前面几周浅浅练了一下最小生成树和二分图的题（最小生成树还有好几题没写，好难，回头再补）。连通性问题这块我还是一点没学过。所以这周还是先看看连通性问题这块知识。

2023-11-10（周五）

这个星期比较懒，前面都没怎么学。今天才开始。

今天看的资料:双连通分量 - OI Wiki (oi-wiki.org),割点和桥 - OI Wiki (oi-wiki.org)

学习的内容是用Tarjan算法求图中的割点和边。

算法中dfn数组其实就是存的每个数再dfs序中的出现位置，low数组用它来存储不经过其父亲能到达的最小的时间戳。

结论也很简单 节点u是节点v的父节点

1.LOWv>=DFNu则u是割点。

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

求割点比求桥要多判断一些东西。为顶点的状态要单独拿出来判断。而且这道题可能不是联通图，所以要每个点都判断一些访问过没有，没有访问过就继续以这个点为顶点调用函数。

好像学会了，但是写起来肯定还是要翻板子。

周末有事小摆一周