Graph Theory - Strongly Connected Component Condensation + Topological Sort

Tarjan算法是一种用于查找已知图中的强连通分量的方法
时间复杂度：O（n+m）//n为点数,m为边数
解法一：并查集维护

#include<bits/stdc++.h>
using namespace std;
#define N 100010
struct edge{
    
    int u, v, nxt;
}e[N];
queue <int> q;
int head[N], cnt, n, m, x, y, vis[N], f[N], c[N], s[N], r[N], ans = 1, W[N];
inline void add(int u, int v){
    
    e[++cnt].u = u;//注意要把 u 也给加上,后面需要调用
    e[cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
int anc(int x){
    
    if(x == f[x]) return x;
    return f[x] = anc(f[x]);
}//并查集模板
void dfs(int u){
    
    for(int i = head[u]; i; i = e[i].nxt){
    
        int v = e[i].v;
        if(!vis[v]){
    //如果没搜索
            vis[v] = vis[u] + 1;//记录“深度”
            dfs(v);//继续搜
        }
        int fu = anc(u), fv = anc(v);//anc is the union function
        if(vis[fv] > 0){
    //Must be in search
            if(vis[fu] < vis[fv]) f[fv] = fu;
            else f[fu] = fv;//注意这里,The depth is small for the father
        }
    }
    vis[u] = -1;//mark search done
    return;
}
int main(){
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) f[i] = i, scanf("%d", W + i);
    for(int i = 1; i <= m; ++i){
    
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for(int i = 1; i <= n; ++i){
    
        if(!vis[i]){
    //If this point has not been searched, continue to search
            vis[i] = 1;
            dfs(i);
        }
    }
    for(int i = 1; i <= n; ++i) c[anc(i)] += W[i];//Reduced point weight processing
    memset(head, 0, sizeof(head));
    cnt = 0;//Here to clear-v-
    for(int i = 1; i <= m; ++i){
    
        x = f[e[i].u], y = f[e[i].v];//Since it has all been traversed above anc 函数了,这里直接调用即可
        if(x != y) add(x, y), r[y]++;//Do not connect edges without a strongly connected component
    }
    for(int i = 1; i <= n; ++i){
    
        if(i == f[i] && !r[i]) q.push(i), s[i] = c[i];
    }//s[i] 是 dp 数组
    while(!q.empty()){
    
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].nxt){
    
            int v = e[i].v;
            s[v] = max(s[v], s[u] + c[v]);
            if(--r[v] == 0) q.push(v);
        }
        ans = max(ans, s[u]);
    }//toposort 模板
    printf("%d", ans);
    return 0;
}

tarjan 缩点

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 15;
int n, m, idx, tim, top, s;
int p[maxn], head[maxn], Scc_id[maxn], dfn[maxn], low[maxn];
//DFN(u)为节点uThe sequence number when the search was found(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号 
//Scc_idis which strongly connected component the final node belongs to,Scc_id[y]=1,则y节点为1Points in the strongly connected components
//p最终为Scc总权值
int stac[maxn], vis[maxn];//The stack is only used to indicate whether there is a parent-child relationship at this time 
int h[maxn], in[maxn], dist[maxn];
struct EDGE
{
    
	int to; int next; int from;
}edge[maxn * 10], ed[maxn * 10];//原图、新图
void add(int x, int y)
{
    
	edge[++idx].next = head[x];
	edge[idx].from = x;
	edge[idx].to = y;
	head[x] = idx;
}
void tarjan(int x)
{
    
	low[x] = dfn[x] = ++tim;
	stac[++top] = x; vis[x] = 1;
	for (int i = head[x]; i; i = edge[i].next)
	{
    
		int v = edge[i].to;
		if (!dfn[v]) {
    
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v])
		{
    
			low[x] = min(low[x], low[v]);
		}
	}
	if (dfn[x] == low[x])
	{
    
		int y;
		while (y = stac[top--])
		{
    
			Scc_id[y] = x;
			vis[y] = 0;
			if (x == y) break;
			p[x] += p[y];
		}
	}
}
int topo()
{
    
	queue <int> q;
	int tot = 0;
	for (int i = 1; i <= n; i++)
		if (Scc_id[i] == i && !in[i])
		{
    
			q.push(i);//The strongly connected component root node and in-degree is 0的节点入队
			dist[i] = p[i];//dist为dp数组,以下标为iThe maximum weight of the point
		}
	while (!q.empty())
	{
    
		int k = q.front(); q.pop();
		for (int i = h[k]; i; i = ed[i].next)
		{
    
			int v = ed[i].to;
			dist[v] = max(dist[v], dist[k] + p[v]);
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, dist[i]);
	return ans;
}
int main()
{
    
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i]);
	for (int i = 1; i <= m; i++)
	{
    
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= m; i++)
	{
    
		int x = Scc_id[edge[i].from], y = Scc_id[edge[i].to];
		if (x != y)//如果xyDoes not belong to a strong connectivity component,Edges are required
		{
    
			ed[++s].next = h[x];ed[s].to = y;ed[s].from = x;//add(x,y) s为新idx
			h[x] = s;in[y]++;
		}
	}
	printf("%d", topo());
	return 0;
}