关于Tarjan

我真是猪脑子哇

学姐讲的全被我吃了

qwq

今天又温习了一下， 觉得还是写下来比较好

毕竟我的记忆力

犹如冬风

不仅刷刷刷的还飕飕飕的

关于割点与割边（桥）：

割点：删它及其连边去之后图变为不连通

能够成为割点的条件： 1.对于根节点，有两棵或以上子树 2.对于非根非叶节点， 某棵子树没有指向u的祖先的回边

割边：删掉这条边之后图变为不连通

成为割边的条件：(u,v)为树边且low[v]>dfn[u]时   原因： 表示v节点只能通过该边与u相连

例题：洛谷P3388 【模板】割点（割顶）

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 100010
using namespace std;
struct node {
    int next, to;
}e[N * 2];
int n, m, idx, cnt, tot;
int head[N], dfn[N], low[N];
bool cut[N];
void add (int x, int y) {
    e[++cnt].next = y;
    e[cnt].to = head[x];
    head[x] = cnt;
}
void tarjan (int u, int fa) {
    dfn[u] = low[u] = ++idx;
    int child = 0;
     for (int i = head[u]; i; i = e[i].to) {
         int nx = e[i].next;
         if (!dfn[nx]) {
             tarjan (nx, fa);
             low[u] = min (low[u], low[nx]);
             if (low[nx] >= dfn[u] && u != fa) 
                 cut[u] = 1;
             if (u == fa) child++;
         }
        else low[u] = min (low[u], dfn[nx]);
    }
    if (child >= 2 && u == fa)
        cut[u] = 1;
}
int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf ("%d%d", &a, &b);
        add (a ,b);
        add (b, a);
    }
    for (int i = 1; i <= n; i++) 
        if (!dfn[i])
            tarjan (i, i);
    for (int i = 1; i <= n; i++) 
        if (cut[i])
            tot++;
    printf ("%d
", tot);
    for (int i = 1; i <= n; i++)
        if (cut[i])
            printf ("%d ", i);
    return 0;
}

关于强连通分量与缩点：

非强连通图的极大强联通子图（哪个lian通无所谓）

要用到栈

例题：洛谷P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量

代码：

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100000;
int n, m, cnt, head[N], dfn[N], low[N], zhan[N], top, idx, belon[N], size[N], out[N], ans, num, js, tot, sum, vis[N];
struct node {
    int nxt, to;
}e[N << 1];
void add(int x, int y) {
    e[++cnt].nxt = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
void tarjan(int x) {
    dfn[x] = low[x] = ++idx;
    zhan[++top] = x;
    vis[x] = 1;
    for(int i = head[x]; i; i = e[i].nxt) {
        int t = e[i].to;
        if(!dfn[t]) tarjan(t), low[x] = min(low[t], low[x]);
        else if(vis[t]) low[x] = min(low[x], dfn[t]);
    }
    if(dfn[x] == low[x]) {
            num++; sum = 0;
            while(zhan[top] != x) sum++, vis[zhan[top]] = 0, belon[zhan[top--]] = num;
            sum++; belon[x] = num; top--;
            size[num] = sum;
        }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i++) 
        for(int j = head[i]; j; j = e[j].nxt)
            if(belon[e[j].to] != belon[i]) out[belon[i]]++;
    for(int i = 1; i <= num; i++)
        if(!out[i]) ans = size[i], js++;
    if(js == 1) printf("%d
", ans);
    else printf("0
");
    return 0;
}

注意更新的是x的low

缩点：就是把low相同的所有点缩为一个点

关于双连通分量：

貌似不是很常用的亚子

对于一个无向图的子图， 当删除其中任意一条边后， 不改变图的连通性， 这样的子图叫边的双联通子图。而当子图的边数达到最大时， 叫做边的双联通分量

怎样求双连通分量：

对于一个无向图， 当我们把图中所有的割边去掉以后， 剩下的每一个区域就是我们要求的边的双连通分量。