Tarjan * 4 | Yammer's BLOG

关于 $Tarjan$ 的四种常见应用场景

割点：

Code

void tarjan(int u, int fa){  // 割点
    def[u] = low[u] = ++ in;
    int num = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i];
        if(!def[v]){
            num ++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(fa != u && low[v] >= def[u] && !ok[u]){
                ok[u] = 1;
                ans ++;
            }
        }else if(v != fa){
            low[u] = min(low[u], def[v]);
        }
    }
    if(u == fa && num >= 2 && !ok[u]){
        ok[u] = 1;
        ans ++;
    }
}

去年写过就不赘述了，其中注意的是已经走过的点的更新方式。

割边：

与割点的性质相同，故名思意将该边删除后将该边存在的一个连通分量分成了两个连通分量。割边的代码与割点一致，区别仅在判断 $if(low[v] > dfn[u])$ ，即 $u → v$ 的边是割边无法使得 $v$ 通过其他路径到达 $u$ , 这里为了方便记录割边的两个端点，使用链式前向星记录邻接表，并且对于割边的两点标记 $st[i] = st[i ^ 1] = 1$ 。

洛谷割边模板

Code

void tarjan(int u, int fa){   //割边
	dfn[u] = low[u] = ++ in;
	for(int i = h[u]; ~i; i = ne[i]){
		int v = e[i];
		if(!dfn[v]){
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u]){
				if(!st[i]) ans ++;
				st[i] = st[i ^ 1] = 1;
			}
		}else if(v != fa){
			low[u] = min(low[u], dfn[v]);
		}
	}
}

缩点：

缩点即在一个有向图中，将带环路径压缩成一个结点方便后续操作。
具体操作是在 $Tarjan$ 的基础上给每个经过的结点入栈，当 $if(low[u] == dfn[u])$ 时说明有一条路径为 $u→v→...→u$ ,说明存在一个以 $u$ 为起始的环，那么我们就可以将此时的栈顶结点全部标记成统一的标记，以下代码中的标记用 $id[u]$ 表示该结点隶属于哪一组，同一组的结点即可表示为一个环用 $u$ 代替表示即称为缩点。如果环上有权值的话也可以将换上的权值全部转移到 $u$ 上。

洛谷缩点模板

Code

void tarjan(int u){  // 缩点
	dfn[u] = low[u] = ++ in;
	sta[++ top] = u; st[u] = 1;
	for(int i = h[u]; ~ i; i = ne[i]){
		int v = e[i];
		if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(st[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		int v;
		t ++;
		do{
			v = sta[top --];
			st[v] = 0;
			id[v] = t;
		}while(v != u);
	}
}

2-sat:

有一种抽象的概念，假设 $(a为真 || b 为假)$ ，那么我们可以从 $a为假推出b为假$ 和 $b为真推出a为真$ 即 $!a→!b$ 和 $b→a$ , 我们可以将这种有向关系转换成一条条的有向边并且标记每个联通块中每个结点的标记，假若 $a和!a$ 属于同种标记则说明 $a和!a$ 同时存在，而实际上这是不可能的，所以最终的条件不能全部满足。

通过抽象出有向边后，我们通过 $Tarjan$ 的缩点处理连通块，最后查看一个连通块中一个元素的对立两种情况是否会在该连通分量中同时存在而判断若干种逻辑条件能否存在。通过以下模板题练习。

洛谷2-sat模板

Code

#include "bits/stdc++.h"
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e6 + 10, MOD = 1e9 + 7;
int h[N], ne[N], e[N], cnt;
int low[N], dfn[N], st[N], in, sta[N], top, id[N], t;
int ans[N];
void add(int a, int b){
	e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void tarjan(int u){
	dfn[u] = low[u] = ++ in;
	sta[++ top] = u; st[u] = 1;
	for(int i = h[u]; ~ i; i = ne[i]){
		int v = e[i];
		if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(st[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		int v;
		t ++;
		do{
			v = sta[top --];
			st[v] = 0;
			id[v] = t;
		}while(v != u);
	}
}
int main(){
	// ios::sync_with_stdio(0); cin.tie(0);
	memset(h, -1, sizeof h);
	int n, m; scanf("%d%d", &n, &m);
	while(m --){
		int i, a, j, b; scanf("%d%d%d%d", &i, &a, &j, & b);
		add(i * 2 + !a, j * 2 + b);
		add(j * 2 + !b, i * 2 + a);
	}
	for(int i = 2; i < n * 2 + 2; ++ i){
		if(!dfn[i]) tarjan(i);
	}
	// for(int i = 1; i <= n + n + 1; ++ i) cout << id[i] << " \n"[i == n + n];
	for(int i = 1; i <= n; ++ i){
		if(id[i * 2] == id[i * 2 + 1]){
			puts("IMPOSSIBLE");
			return 0;
		}
		ans[i] = id[i * 2] > id[i * 2 + 1];
	}
	puts("POSSIBLE");
	for(int i = 1; i <= n; ++ i){
		printf("%d ", ans[i]);
	}
}

2-sat练习题

Code

#include "bits/stdc++.h"
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e6 + 10, MOD = 1e9 + 7;
int h[N], ne[N], e[N], cnt;
int low[N], dfn[N], st[N], in, sta[N], top, id[N], t;
int ans[N];
void add(int a, int b){
	e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void tarjan(int u){
	dfn[u] = low[u] = ++ in;
	sta[++ top] = u; st[u] = 1;
	for(int i = h[u]; ~ i; i = ne[i]){
		int v = e[i];
		if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(st[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		int v;
		t ++;
		do{
			v = sta[top --];
			st[v] = 0;
			id[v] = t;
		}while(v != u);
	}
}
int main(){
	// ios::sync_with_stdio(0); cin.tie(0);
	memset(h, -1, sizeof h);
	int n, m; cin >> n >> m;
	while(m --){
		int a, b; cin >> a >> b;
		add(a, b + ((b & 1) ? 1 : -1));
		add(b, a + ((a & 1) ? 1 : -1));
	}
	for(int i = 1; i <= n * 2; ++ i){
		if(!dfn[i]) tarjan(i);
	}
for(int i = 1; i <= n; i ++){
	if(id[i * 2] == id[i * 2 - 1]){
		puts("NIE");
		return 0;
	}
	ans[i] = ((id[i * 2] < id[i * 2 - 1]) ? i * 2 : i * 2 - 1);
}
for(int i = 1; i <= n; ++ i){
	cout << ans[i] << '\n';
}

}

还有一条Div4的H题
cf(2-sat)

Code

#include "bits/stdc++.h"
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
int h[N], ne[N], e[N], cnt, t;
int low[N], dfn[N], st[N], in, sta[N], top, id[N];
void add(int a, int b){
	 e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void tarjan(int u){
	dfn[u] = low[u] = ++ in;
	sta[++ top] = u; st[u] = 1;
	for(int i = h[u]; ~ i; i = ne[i]){
		int v = e[i];
		if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if(st[v]) low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]){
		int v;
		t ++;
		while(v = sta[top --]){
			id[v] = t;
			st[v] = 0;
			if(v == u) break;
		}
	}
}
void init(){
	cnt = in = top = t = 0;
	memset(h, -1, sizeof h);
	memset(ne, 0, sizeof ne);
	memset(st, 0, sizeof st);
	memset(e, 0, sizeof e);
	memset(dfn, 0, sizeof dfn);
	memset(low, 0, sizeof low);
	memset(id, 0, sizeof id);
}
int s[4][510];
void solve(){
	init();
	int n; cin >> n;
	for(int i = 1; i <= 3; ++ i){
		for(int j = 1; j <= n; ++ j){
			cin >> s[i][j];
		}
	}
	for(int ii = 1; ii <= n; ++ ii){
		for(int i = 1; i < 3; ++ i){
			for(int j = i + 1; j <= 3; ++ j){
				int u = s[i][ii], v = s[j][ii];
				int a = abs(u), b = abs(v);
				add(a * 2 + (u < 0), b * 2 + (v > 0));
				add(b * 2 + (v < 0), a * 2 + (u > 0));
			}
		}
	}
	for(int i = 1; i <= n + n; ++ i){
		if(!dfn[i]) tarjan(i);
	}
	for(int i = 1; i <= n; ++ i){
		if(id[i * 2] == id[i * 2 + 1]) {
			cout << "NO\n";
			return ;
		}
	}
	cout << "YES\n";
}
int main(){
	//ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	while(n--) solve();
	return 0;
}