概念:有向图中的一部分点,其中所有点都可以互相到达时,称为强连通分量。
把一个有向图中所有的强连通分量各缩成一个点后,剩下的图中没有环,是一个有向无环图(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; }