图论——强连通分量缩点+拓扑排序

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

#include
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 是并查集函数
        if(vis[fv] > 0){//一定要是搜索中的
            if(vis[fu] < vis[fv]) f[fv] = fu;
            else f[fu] = fv;//注意这里，深度小的为父亲
        }
    }
    vis[u] = -1;//标记搜索完
    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]){//如果这个点还没搜索就要继续搜
            vis[i] = 1;
            dfs(i);
        }
    }
    for(int i = 1; i <= n; ++i) c[anc(i)] += W[i];//缩点权值处理
    memset(head, 0, sizeof(head));
    cnt = 0;//这里要清零哦-v-
    for(int i = 1; i <= m; ++i){
        x = f[e[i].u], y = f[e[i].v];//由于在上面已经全部遍历过 anc 函数了，这里直接调用即可
        if(x != y) add(x, y), r[y]++;//不在一个强连通分量就连边
    }
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

tarjan 缩点

#include
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)为节点u搜索被搜索到时的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号 
//Scc_id为最终节点属于哪个强连通分量，Scc_id[y]=1,则y节点为1号强联通分量中的点
//p最终为Scc总权值
int stac[maxn], vis[maxn];//栈只为了表示此时是否有父子关系 
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);//将强联通分量根节点并且入度为0的节点入队
			dist[i] = p[i];//dist为dp数组，以下标为i的点的最大权值
		}
	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)//如果xy不属于一个强联通分量，则需要连边
		{
			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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100