Tarjan 算法求强连通分量

概念:有向图中的一部分点,其中所有点都可以互相到达时,称为强连通分量。

把一个有向图中所有的强连通分量各缩成一个点后,剩下的图中没有环,是一个有向无环图(DAG)。有向无环图拓扑序一定,可以进行图上dp/记忆化搜索等操作而不用担心后效性的问题。

Tarjan算法的流程如下:
(1)按照DFS序(dfn[])为节点排序,同时维护当前节点能到达的祖先中DFS序的最小值(low[],初值设为dfn)。
(2)用一个栈维护和当前节点有祖先/后代关系的节点,并记录一个节点是否在栈中(S、inS[])。
(3)在DFS的过程中如果遇到了在栈中的节点,则可以认定该节点为当前节点的祖先,记录它的DFS序。每一个子节点DFS返回后记录它的最小值并与当前节点最小值取最小。
(4)如果在遍历完所有没有访问过的子节点后这个节点的dfn值还是和low值相等,则可以确定,当前栈中该节点及以上的元素共同组成了一个强连通分量(可以只有一个节点),将其取出栈中。

stack<int> S;                        // 栈相关信息
bool inS[MaxN];

int dfn[MaxN], stime, low[MaxN];     // Tarjan相关信息(stime指搜索时间)

int blockcnt, belong[MaxN];          // 分量相关信息
vector<int> blocks[MaxN];

void dfs(int u) {
    dfn[u] = low[u] = ++stime;                                // 记录dfs序
    S.push(u);                                                // 当前节点入栈
    inS[u] = true;
    for (node* p = h[u]; p != nullptr; p = p->next) {
        int v = p->v;                                         // 取下一个节点
        if (dfn[v] == 0) {                                    // 如果下一个节点没有访问过
            dfs(v);                                           // 递归
            low[u] = min(low[u], low[v]);                     // low取最小
        }
        else if (inS[v])                                      // 如果下一个节点在栈中
            low[u] = min(low[u], dfn[v]);                     // low取与dfn的最小
    }
    if (dfn[u] == low[u]) {                                   // 如果递归完成后dfn和low还是相等
        blockcnt++;                                           // 把当前栈中节点记录到一个块里
        int cur;
        do {
            cur = S.top(); S.pop();                           // 出栈
            inS[cur] = false;
            blocks[blockcnt].push_back(cur);                  // 记录分量信息
            belong[cur] = blockcnt;
        } while (cur != u);                                   // 一直出栈直到取出当前节点为止
    }
}

强连通分量缩点时,将分量内部的边省去,将分量之间的边加入另一个图中。

node* dag[MaxN];
void shrink() {
    for (int u = 1; u <= n; u++) {                             // 遍历原图中的起始点
        for (node* p = h[u]; p != nullptr; p = p->next) {      // 遍历从起始点出发的每一条边
            int v = p->v;
            if (belong[u] != belong[v])                        // 如果这条边的起止点不在一个分量里
                addedge(belong[u], belong[v], dag);            // 就把这条边加到新图中
        }
    }
}

时间复杂度:DFS\(O(n)\),缩点\(O(m)\)

例题:P3387 【模板】缩点(强连通分量缩点+记忆化搜索)

/*
DOCUMENT NAME "20180711-luogu3387.cpp"
CREATION DATE 2018-07-11
SIGNATURE CODE_20180711_LUOGU3387
COMMENT 【模板】缩点
*/

#include <cstdlib>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int infinity = 1e8;
const int MaxN = 1e4 + 10, MaxM = 1e5 + 10;

int n, m;
int weight[MaxN];

struct node {
    int v;
    node* next;
};

node* h[MaxN];
node mem[2 * MaxM], *memtop = mem;
#define ALLOCATE (++memtop)

void addedge(int u, int v, node** h = ::h) {
    node* p = ALLOCATE;
    p->v = v;
    p->next = h[u];
    h[u] = p;
}


stack<int> S;
bool inS[MaxN];
int dfn[MaxN], stime, low[MaxN];
int blockcnt, belong[MaxN];
int blockweight[MaxN];
vector<int> blocks[MaxN];
void dfs(int u) {
    dfn[u] = ++stime;
    low[u] = stime;
    S.push(u);
    inS[u] = true;
    for (node* p = h[u]; p != nullptr; p = p->next) {
        int v = p->v;
        if (dfn[v] == 0) {
            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]) {
        blockcnt++;
        int cnt;
        do {
            cnt = S.top(); S.pop();
            inS[cnt] = false;
            blocks[blockcnt].push_back(cnt);
            blockweight[blockcnt] += weight[cnt];
            belong[cnt] = blockcnt;
        } while (cnt != u);
    }
}


node* dag[MaxN];
void shrink() {
    for (int u = 1; u <= n; u++) {
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v;
            if (belong[u] != belong[v])
                addedge(belong[u], belong[v], dag);
        }
    }
}

int ans[MaxN];
int search(int u) {
    if (ans[u] != -1)
        return ans[u];
    else {
        ans[u] = 0;
        for (node* p = dag[u]; p != nullptr; p = p->next) {
            int v = p->v;
            ans[u] = max(ans[u], search(v));
        }
        ans[u] += blockweight[u];
        return ans[u];
    }
}



int main(int argc, char* argv[]) {

    memset(ans, -1, sizeof(ans));

    cin >> n >> m;
    int u, v, w;
    for (int i = 1; i <= n; i++)
        cin >> weight[i];
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        addedge(u, v);
    }

    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0)
            dfs(i);
    shrink();

    int ans = 0;
    for (int i = 1; i <= blockcnt; i++) {
        ans = max(ans, search(i));
    }

    cout << ans << endl;

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注