$Tarjan$算法的核心思路是：对于每一个点，维护一个时间戳$dfn$以及一个最早可回溯祖先$low$，这两个东西的初始化依靠dfs算法实现。$dfn$表示在dfs中被搜索到的时间戳，而$low$表示的是通过该点的子边所能到达的最早祖先。同时维护一个栈，每次dfs时将点入栈，以此查询父子关系。有以下三种算法：

1) 如果发现一个点对应的$low$=$dfn$，那么在当前已入栈的点及其子边所构成的子图中，以这个点为始点的子图就组成了一个强连通分量。

2) 对于一条边$(u,v)$，对应的$low[v]\ge dfn[u]$；或者$u$为根节点，且拥有2个以上的子节点，那么$u$是一个割点。

3) 对于一条边$(u,v)$，对应的$low[v]>dfn[u]$，并且$(u,v)$不是重边，那么$(u,v)$是一个桥。

割点

模板P3388

最坑的地方在于，对于边$(u,v)$，如果$v$已经被访问过了，在更新$low[u]$的时候不再用$low[u]=min(low[u], low[v])$，而用的是$$ low[u] = min(low[u],dfn[v])$$ 具体原因是$low[v]$可能会指向$v$所能访问到的另外一个祖先，如果继续用$low[v]$更新，就可能跳出当前的访问路径，跑到其他地方去了，这显然对于割点的判断是有影响的。因为就算$v$存在于其他强连通分量中，只要$(u,v)$满足$low[v]\ge dfn[u]$，去掉$u$之后依然能够将图断开。桥也同理，因为依赖的不是最后结果而是过程中对$low$和$dfn$的比较。因此要记住这个坑点。

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

const int MAXN = 100010;

struct EDGE {
    int to, next;
} edge[MAXN*2];

int cnt = 0, n, m, id = 0, tot = 0, x, y;
int last[MAXN], low[MAXN], dfn[MAXN];
bool cut[MAXN];

void build_edge(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = last[u];
    last[u] = cnt;
    return;
}

void Tarjan(int o, int fa) {
    dfn[o] = low[o] = ++id;
    int c_cnt = 0;
    for(int i=last[o]; i; i=edge[i].next) {
        int p = edge[i].to;
        if(!dfn[p]) {
            Tarjan(p, fa);
            low[o] = min(low[o], low[p]);
            if(o!=fa && low[p]>=dfn[o]) {
                cut[o] = true;
            }
            if(o == fa)
                c_cnt++;
        } else
        low[o] = min(low[o], dfn[p]);
    }
    if(o==fa && c_cnt>=2)
        cut[o] = true;
    return;
}

int main() {
    memset(cut, 0, sizeof(cut));
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> x >> y;
        build_edge(x, y);
        build_edge(y, x);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i]) Tarjan(i, i);
    for(int i=1; i<=n; i++)
        if(cut[i]) tot++;
    cout << tot << endl;
    for(int i=1; i<=n; i++)
        if(cut[i]) cout << i << " ";
    return 0;
}

桥

桥其实差不多，由于没有模板所以就不打标程上来了。代码没测试，我也不知是不是对的，大概看看就好。要注意的是特判重边，因为对于一个桥$(u,v)$，当访问$(v,u)$的时候如果不特判的话就会直接把这个无向边认作环，实际上这个切掉这个无向边依然能把图一分为二。

void Tarjan(int u, int fa) {
    dfn[u] = low[u] = ++id;
    for(int i=last[u]; i; i=edge[i].next) {
        int v = edge[i].to;
        if(v == fa) continue;
        if(!dfn[v]) {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u])
                cut[i] = true;
        } else if(v != fa) // 或者改成非反向边的判定条件
            low[u] = min(low[u], dfn[v]); //坑
    }
    return;
}

缩点

一道有缩点的模板P3387

这道题就是$Tarjan+DAGdp$解决，因为缩点之后就变成无环图了。$DAGdp$之前有写到过就不说了。 缩点就是判断强连通分量，把它们全部用一个点来替代，然后建立新图。具体可以用染色实现。

缩点的时候只要遇到$low[u]=dfn[u]$，那么就从之前的栈里头一直取点，一直到把$u$给取出来为止，然后把它们全部染色。另外，在更新$low$的时候$else$后跟的$low[u]=min(low[u], low[v])$可以换成$low[u]=min(low[u], dfn[v])$,因为两者在结果上是等价的，只是前者的适用范围仅有强连通分量，而不能用于判断割点和桥而已。所以以后还是直接打后者算了，免得到时候搞忘坑点。

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

const int MAXN = 10010;

struct EDGE {
    int from, to, next;
} edge[MAXN*10], _edge[MAXN*10];

int last[MAXN], _last[MAXN], cnt = 0;
int dfn[MAXN], low[MAXN], id = 0;
int s[MAXN], top = 0;
bool ins[MAXN];
int n, m, x, y, p[MAXN], clr[MAXN], f[MAXN], in[MAXN];

void build_edge(int u, int v) {
    edge[++cnt].from = u;
    edge[cnt].to = v;
    edge[cnt].next = last[u];
    last[u] = cnt;
    return;
}

void Tarjan(int u) {
    dfn[u] = low[u] = ++id;
    s[++top] = u;
    ins[u] = true;
    for(int i=last[u]; i; i=edge[i].next) {
        int v = edge[i].to;
        if(!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int v;
        while(v = s[top--]) {
            clr[v] = u;
            ins[v] = false;
            if(u == v) break;
            p[u] += p[v];
        }
    }
    return;
}

void toposort() {
    queue<int> q;
    for(int i=1; i<=n; i++)
        if(i==clr[i] && !in[i]) {
            q.push(i);
            f[i] = p[i];
        }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=_last[u]; i; i=_edge[i].next) {
            int v = _edge[i].to;
            f[v] = max(f[v], f[u]+p[v]);
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
    return;
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> p[i];
    for(int i=1; i<=m; i++) {
        cin >> x >> y;
        build_edge(x, y);
    }
    cnt = 0;
    for(int i=1; i<=n; i++)
        if(!dfn[i]) Tarjan(i);
    for(int i=1; i<=m; i++) {
        int u = clr[edge[i].from], v = clr[edge[i].to];
        if(u != v) {
            _edge[++cnt].to = v;
            _edge[cnt].next = _last[u];
            _last[u] = cnt;
            in[v]++;
        }
    }
    toposort();
    int ans = 0;
    for(int i=1; i<=n; i++)
        ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

不要再忘记$Tarjan$了，重新从头学一遍太痛苦了哇！