图的连通性

强连通分量

Tarjan算法

求强连通分量。
算法思路：在DFS森林上进行操作，不断地整合点成块然后切割块，使得只考虑经过但未被切割的点，这样就忽略了横向边的影响。只要一个点能返祖(自己或经过子树)到更小的时间点，那么这个点就属于某一个强连通块；否则该点就作为这个强连通块的第一个被搜索到的点，强连通块的其他点的返祖最小时间点也一定是该点，那么可以切割并记录该强连通分量。
时间复杂度 $O(N+M)$

vector<int> edge[N];

int dfn[N], low[N], ins[N], idx = 0; //分别代表到i点的时间，返祖最小时间，是否在堆中(或被切割)
stack<int> stk; //记录经过但待分类的点
vector<vector<int>> scc; //记录强连通分量

void dfs(int u){
    dfn[u] = low[u] = ++ idx;
    ins[u] = true;
    stk.push(u);
    for (auto v : edge[u])
        if (!dfn[v]){ //没搜过
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else{
            if (ins[v]) low[u] = min(low[u], dfn[v]); //不考虑指向另外强连通分量的横向边，只考虑状态未定的点
        }
    if (dfn[u] == low[u]){ //强连通分量的First节点
        vector<int> c;
        while (true){
            int v = stk.top(); //取出
            c.push_back(v); //记录
            ins[v] = false;//被切割
            stk.pop(); //删除
            if (v == u) break;
        }
        //sort(c.begin(), c.end());
        scc.push_back(c);
    }
}

Kosaraju 算法

相比于Tarjan算法，只需要记录一个点有没有救，即纳入强连通分量的潜力。

Important

DAG(有向无环图)DFS一遍的出栈顺序是反图的拓扑序
有向图 SCC缩点 -> DAG
推论：在缩点完的DAG里一定是个源点(没有入度)

算法思路：2遍DFS，dfs_1对正图求出栈顺序out，然后翻转out，遍历对其dfs_2对反图求出所有以该源点的强连通分量。
时间复杂度 $O(N+M)$

vector<int> e[N], erev[N]; //原图 反图

int vis[N];
vector<int> c, out;

void dfs_1(int u){
    vis[u] = true;
    for (auto v : e[u])
        if (!vis[v]) dfs_1(v);
    out.push_back(u);
}

void dfs_2(int u){
    vis[u] = true;
    c.push_back(u);
    for (auto v : erev[u])
        if (!vis[v]) dfs_2(v);
}

void solve() {
    int n, m;
    cin >> n >> m;
    while (m -- ){
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        erev[y].push_back(x);
    }   
    for (int i = 1; i <= n; i ++ )
        if (!vis[i]) dfs_1(i);
    reverse(out.begin(), out.end());
    memset(vis, 0, sizeof vis);
    for (auto u : out)
        if (!vis[u]){
            c.clear();
            dfs_2(u);
        }
}

(桥)割边和割点

桥

Tarjan算法
对于一个点X，考虑其子树的所有返祖边返不到自己先祖

vector<pair<int, int>> e[N]; // u -> v 边的编号为second

int dfn[N], low[N], idx = 0;

vector<int> bridge;
//fa -> u 的 id
void dfs(int u, int id){
    dfn[u] = low[u] = ++ idx;
    for (auto [v, id2] : e[u]){
        if (!dfn[v]) dfs(v, id2);
        if (id != id2) low[u] = min(low[u], low[v]); //判重 使用id可以判重 但fa不能判重
    }
    if (dfn[u] == low[u] && id != -1){ //注意id != -1
        bridge.push_back(id);
    }
}

void solve(){
    int n, m;
    for (int i = 1; i <= n; i ++ ) e[i].clear(), dfn[i] = low[i] = 0; //初始化
    for (int i = 1; i <= m; i ++ ){
        int u, v;
        cin >> u >> v;
        e[u].push_back({v, i});
        e[v].push_back({u, i});
    }
    bridge.clear();
    for (int i = 1; i <= n; i ++ ) //考虑多个连通块
        if (!dfn[i]) dfs(i, -1);
    cout << bridge.size() << '\n';
}

割点

思考点与点的关系，不能用dfn[u] == low[v]判断割点

vector<int> e[N];

int dfn[N], low[N], idx, sz;
int cut[N];

void dfs(int u, int fa){
    dfn[u] = low[u] = ++ idx;
    int ch = 0;
    for (auto v : e[u]){
        if (!dfn[v]){
            dfs(v, u);
            ++ ch;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) cut[u] = 1; //是割点   **最关键的判断**
        }else if (v != fa){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (fa == -1 && ch <= 1) cut[u] = 0; //根特殊
    sz += cut[u];
}

//以下是读入，可随意修改
void solve(){
    int n;
    while (cin >> n && n){
        for (int i = 1; i <= n; i ++ ) e[i].clear(), dfn[i] = low[i] = cut[i] = 0; //初始化
        int u;
        while (cin >> u && u){
            while (getchar() != '\n'){ //判断读行
                int v;
                cin >> v;
                e[u].push_back(v);
                e[v].push_back(u);
            }
        }
        idx = sz = 0;
        for (int i = 1; i <= n; i ++ )
            if (!dfn[i]) dfs(i, -1);
        cout << sz << '\n';
    }
}

DP有关

可以直接在缩点过程中DP
样例：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

const int N = 5e5 + 10;
// SCC缩点成DAG进行DP

vector<int> e[N];

int dfn[N], low[N], ins[N], idx = 0;
stack<int> stk;

int cnt, T;
int dp[N], bel[N], vis[N], isd[N];

int val[N], ed[N];

void dfs(int u){
    dfn[u] = low[u] = ++ idx;
    ins[u] = true;
    stk.push(u);
    for (auto v : e[u])
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else{
            if (ins[v]) low[u] = min(low[u], dfn[v]);
        }
    if (dfn[u] == low[u]){
        ++ cnt;
        dp[cnt] = 0, isd[cnt] = 0;
        ++ T;
        vis[cnt] = T;
        int sum = 0, is_ed = 0;
        while (true){
            int v = stk.top();
            ins[v] = false;
            bel[v] = cnt;
            sum += val[v];
            if (ed[v]) {
                is_ed = true;
                //cout << "终点！" << v << '\n';
            }
            for (auto w : e[v])
                if (vis[bel[w]] != T && isd[bel[w]]){
                    is_ed = true;
                    vis[bel[w]] = T;
                    dp[cnt] = max(dp[cnt], dp[bel[w]]);
                }
            stk.pop();
            if (v == u) break;
        }
        dp[cnt] += sum;
        isd[cnt] = is_ed;
        //cout << cnt << ' ' << dp[cnt] << ' ' << isd[cnt] << '\n';
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    while (m -- ){
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
    }
    for (int i = 1; i <= n; i ++ ) cin >> val[i];
    int S, P;
    cin >> S >> P;
    while (P--){
        int x;
        cin >> x;
        ed[x] = true;
    }
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) dfs(i);
    cout << dp[bel[S]];
}

signed main() {
    IOS;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}