Connected Components 连通分量及相关算法

引子

这是一篇久咕之作。

模板

todo

引导

首先，假设我们用的是前向星建图。

struct Edge {
    int u, v, nx; // ,w
} e[MAXN << 1];

int head[MAXN], cntEd;

inline void addEdge(int u, int v) {
    e[cntEd] = {u, v, head[u]};
    head[u] = cntEd++;
}

然后应该写一个DFS。

void tarjan(int u) {
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;

        if ( ) { }
    }
  
    if ( ) { }
}

下面想需要用到什么数组。

int low[MAXN];					//LOWLINK
int dfn[MAXN], idx;			//NUMBER
int stk[MAXN], top;			//STACK for cc
int scc[MAXN], sccnum;	//SCC tags

然后想一下每个数组的意义，填进DFS。


void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;

    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;

        if (!dfn[v]) {    			//如果v结点未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!scc[v]) {		//如果还在栈内
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {			//后代不能找到更浅的点
        sccnum++;
        int x;
        do {
            x = stk[top--];
            scc[x] = sccnum;
        } while (x != u);
    }
}

然后学会怎么用它。


int main() {
    memset(head, -1, sizeof head);
    int n;
  
  	//input & build graph ...
  
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i])
            tarjan(i);
    }
  
  	//scc[v] ...
  
    return 0;
}