# 前置概念

时间戳:搜索时第几个搜索到这个点。如搜索顺序是 1->2->3->6,则 6 的时间戳为 4

# 对于无向图

连通分量:对于图 G 来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图 G 的连通分量(一个点就是最小的连通分量)

最大连通分量:对于图 G 的一个子图,这个子图为图 G 的连通分量,且是图 G 所有连通分量中包含节点数最多的那个,即为 G 的最大联通分量

# 算法流程

个人认为 Tarjan 是提高组范围内最难的一个算法了,我自己说不太明白。。。推荐看看这篇

# 简单应用

# 缩点

有向图强连通分量:在有向图 G 中,如果两个顶点 vi,vj 间(vi>vj)有一条从 vi 到 vj 的有向路径,同时还有一条从 vj 到 vi 的有向路径,则称两个顶点强连通 (strongly connected)。孤立的一个点也是一个强连通分量。

如果有向图 G 的每两个顶点都强连通,称 G 是一个强连通图。有向图的极大强连通子图,称为强连通分量(SCC, Strongly Connected Components)。把每个强联通分量看成一个集合,把每个集合看成一个点,那么所有 SCC 就形成了一个 DAG(有向无环图),就是著名的缩点。

Problem

根据题目意思,我们只需要找出一条点权最大的路径就行了,不限制点的个数。那么考虑对于一个环上的点被选择了,一整条环是不是应该都被选择,这一定很优,能选干嘛不选。很关键的是题目还允许我们重复经过某条边或者某个点,我们就不需要考虑其他了。因此整个环实际上可以看成一个点(选了其中一个点就应该选其他的点)

在处理了环后,我们就重新建立一张图,以每个环为节点(孤立一个点也算也算环的,其实也就是强联通分量了)。在这张图中我们要 dp,显然对于任意边 <u,v>, dp[v] = max(dp[v], dp[u] + new_weight[v])

dp 的时候拓扑排一下序,这也是 DAGdp 的常见 trick 了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10, M = 1e5+10;
struct node {
	int u, v, nxt;
} e[M];
int h[N], tot = 0;
int dfn[N], low[N], tag = 0, top = 0, num = 0;
int n, m, w[N], ww[N], f[N], id[N], s[N], in[N];
void tarjan(int u) {
	
	dfn[u] = low[u] = ++tag;
	s[++top] = u;
	for(int i = h[u], v; i; i = e[i].nxt) {
		v = e[i].v;
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if(!id[v]) low[u] = min(low[u], dfn[v]);
	}
	
	if(dfn[u] == low[u]) {
		++num;
		while(s[top] != u) {
			id[s[top]] = num; ww[num] += w[s[top]]; top--;
		}
		id[s[top]] = num; ww[num] += w[s[top]]; top--;
    }
    
}
int main() {
	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i) scanf("%d", w+i);
	
	for(int i=1; i<=m; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		if(u == v) continue; e[++tot] = {u, v, h[u]}; h[u] = tot;
	}
	for(int i=1; i<=n; ++i) {
		if(!dfn[i]) tarjan(i);
	}
	
	memset(h, 0, sizeof h);
	for(int i=0, t=0; i<tot; ++i) {
		int u = id[e[i].u], v = id[e[i].v];
		if(u == v); else {
			e[++t] = {u, v, h[u]}; h[u] = t;
			++in[v];
		}
	}
	
	queue<int> q;
	for(int i=1; i<=num; ++i) {
		if(!in[i]) q.push(i);
	}
	int ans = 0;
	for(int i=1; i<=num; ++i) f[i] = ww[i], ans = max(ans, f[i]);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = h[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			f[v] = max(f[v], f[u]+ww[v]);
			ans = max(ans, f[v]);
			--in[v];
			if(!in[v]) q.push(v);
		}
	}
	printf("%d\n", ans);
	 
	return 0;
}

# 找割点

割点:去掉无向联通图的某个点后,此图不连通,该点为割点。

Problem

#include <stdio.h>
#include <iostream>
using std::min;
const int N = 22000, M = 110000;
struct node {
	int u, v, next;
} e[M << 1];
int h[N], tot;
int dfn[N], low[N], tag;
int res[N], ans, n, m, fa[N];
void tarjan(int u, int fa) {
	
	dfn[u] = low[u] = ++tag;
	
	int sum = 0;
	for(int i = h[u], v; i; i = e[i].next) {
		v = e[i].v;
		if(v == fa) continue;
		
		if(dfn[v]) low[u] = min(low[u], dfn[v]);
		else {
			++sum;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(fa == -1) continue;
			if(low[v] >= dfn[u]) res[u] = true;
		}
	}
	
	if(fa == -1 and sum > 1) res[u] = true;
	
}
int main() {
	
	//freopen("p3388_4.in", "r", stdin);
	
	scanf("%d%d", &n, &m);
	
	for(int i=1, x, y; i<=m; ++i) {
		scanf("%d%d", &x, &y);
		e[++tot] = (node) {x, y, h[x]}; h[x] = tot;
		e[++tot] = (node) {y, x, h[y]}; h[y] = tot;
	}
	
	for(int i=1; i<=n; ++i)
		if(dfn[i] == 0) tarjan(i, -1);
		
	for(int i=1; i<=n; ++i) if(res[i]) ++ans;
	printf("%d\n", ans);
	for(int i=1; i<=n; ++i) if(res[i]) printf("%d ", i);
	
	return 0;
}
更新于