割点（割顶）¶

讲解¶

割点

在无向联通图$ G=(V,E)$中: 若对于$x∈V$，从图中删去节点$x$以及所有与$x$关联的边之后， \(G$分裂成两个或两个以上不相连的子图，则称\)x$为$G$的割点。

割边

假设有连通图$G$，$e$是其中一条边，如果$G-e$ (在图$G$中去掉边$e$) 是不连通的，则边$e$是图$G$的一条割边。此情形下，$G-e$必包含两个连通分支。

推荐资料

图的割点与割边（超详细！！！） - endl\n - 博客园

例题 #1¶

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

对于全部数据，$1\leq n \le 2\times 10^4$，$1\leq m \le 1 \times 10^5$。

点的编号均大于 $0$ 小于等于 $n$。

tarjan图不一定联通。

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int N=2e5+5;


int cnt,num,br[N],nxt[N],h[N], n,m,to[N],ans,low[N],dfn[N];
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
}

void tarjan(int x,int e){
    dfn[x]=low[x]=++num;
    int child=0;    //局部变量 
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y,e);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]&&x!=e){//>=而不是>  !!! 
                br[x]=1;
            }
            if(x==e)child++;
        }
        low[x]=min(low[x],dfn[y]);

    }
    if(child>1&&x==e)br[x]=1;
} 
signed main(){
    memset (dfn,0,sizeof (dfn));
    memset (h,0,sizeof (h));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
     for (int i=1;i<=n;i++)
        if (dfn[i]==0)
            tarjan (i,i);


    for (int i=1;i<=n;i++)
        if (br[i])
            ans++;
    printf ("%d\n",ans);
    for (int i=1;i<=n;i++)
        if (br[i])
            printf ("%d ",i);

    return 0;
}

例题 #2 [ZJOI2004] 嗅探器¶

题目描述

某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。

蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。

但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。

现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？

输入格式

输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。

接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。

服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。

输出格式

输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。

对于 $100\%$ 的数据，$1\le n\le 2 \times 10^5$，边数不超过 $5 \times 10^5$。

就是求出a,b路径上编号最小的割点。我们在跑vdcc时，如果有≥2给v满足dfn[u]<=low[v]，那么u就是一个割点了。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;



int n,l,r;
struct edge{ int to,nxt; } d[N];
int head[N],cnt=1;
void add(int u,int v){ d[++cnt]=(edge){v,head[u]},head[u]=cnt; }
int dfn[N],low[N],stk[N],id,top,cut[N];
void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++id,stk[++top]=u;
    int flag=0;
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to;
        if( !dfn[v] )
        {
            tarjan(v,fa);
            low[u]=min( low[u],low[v] );
            if( dfn[u]<=low[v] )
            {
                flag++;
                if( u!=fa||flag>=2 )
                {
                    if( dfn[v]<=dfn[r] )    cut[u]=1;
                }
            }
        }
        else    low[u]=min( low[u],dfn[v] );
    }
}
int ans[N];
void solve()
{
    cin >> n;
    while(1){
        itn a=rd,b=rd;
        if(a+b==0)break;
        add(a,b),add(b,a);}
    cin >> l >> r;
    tarjan(l,l);
    for(int i=1;i<=n;i++)
    if( cut[i]&&i!=l&&i!=r )
    {
        cout << i <<endl;
        return ;
    }
    cout << "No solution";
}


signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}