【算法笔记】Kosaraju算法

前言

今天考了一套$Claris$的题
$T1$就是$Claris$用$bitset$配合这个算法把求$SCC$优化到了$\frac{n^2}{32}$
吓得我赶紧来学了学

算法概述

$step \ 1.$ DFS一遍,记录下后序遍历的顺序
$step \ 2.$ 沿后续遍历的逆序、沿反向边再DFS一遍,每一个连通块即为一个SCC

算法解释

设原图为图$G$,将$SCC$缩点后的新图为$G’$
第一遍$DFS$保证了在若某个强连通分量$A$在$G’$中是另一个强连通分量$B$的祖先
那么在后续遍历的逆序中至少存在一个点$A$中的点在$B$中所有点的前面

这样在第二次$DFS$的时候,因为是逆序,所以只能往$G’$中的祖先走
又因为祖先的$SCC$已经标记过了,所以刚好把当前$SCC$搞完,不会有多

这算法太妙了

代码实现

int scc_cnt, vis[N];
vector<int> scc_cnt[N], que;
void DFS0(int w) {
	vis[w] = 0;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS0(to[i]);
		}
	}
	que[++tot] = w;
}
void DFS1(int w) {
	scc[scc_cnt].push_back(w);
	vis[w] = 1;
	for (int i = rev_head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS1(to[i]);
		}
	}
} 
void solve() {
	que.clear();
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS0(i);
		}
	}
	scc_cnt = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = (int)que.size() - 1; ~i; i--) {
		if (!vis[que[i]]) {
			scc_cnt++;
			DFS1(que[i]);
		}
	}
}

使用$bitset$优化

这货复杂度是$O(m)$的
不难发现算法瓶颈在查找与某个点相邻的所有点中还没有被访问过的点
这个可以用$bitset$压位并配合__builtin开头的系列函数优化到$O(\frac{n^2}{32})$
例题的话,可以参考:友好城市

【日常小测】友好城市

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 2438】[中山市选2011] 杀人游戏

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2438
数据生成器:http://paste.ubuntu.com/19584806/
PS:此题的随机数据不容易拍出错QAQ

来练习Tarjan的scc,然而此题细节比较多,被卡了好久QAQ

很明显,如果一个scc中知道了一个点,则其他点都可以安全推出
所以我们只需要搞出入度为零的scc有多少个即可

然而还有一个坑:
如果最后问得只剩一个单独的点了,这个点是不需要询问的
所以遇到这种单独的点,并且他连向的点的入度都不为一的话,ans -= 1

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

const int MAXN = 300000+9;

int n,m,to[MAXN],nxt[MAXN],head[MAXN];
int num[MAXN],lowlink[MAXN],in[MAXN],vout;
int scc_num[MAXN],scc_sz[MAXN],scc_cnt;
stack<int> sta;

inline void AddEdge(int u, int v){
	static int T = 0; 
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

void DFS(int w) {
	static int tot = 0; sta.push(w);
	num[w] = lowlink[w] = ++tot;
	for (int i=head[w];i;i=nxt[i]) {
		if (!num[to[i]]) DFS(to[i]), lowlink[w] = min(lowlink[w], lowlink[to[i]]);
		else if (!scc_num[to[i]]) lowlink[w] = min(lowlink[w], lowlink[to[i]]);
	}
	if (lowlink[w] == num[w]) {
		scc_cnt += 1;
		while (true) {
			int nw = sta.top(); sta.pop();
			scc_num[nw] = scc_cnt;
			scc_sz[scc_cnt]++;
			if (nw == w) break;
		}
	}
}

int main(){
	n = read(); m = read(); if (n==1) {printf("1.000000\n"); return 0;}
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), AddEdge(u,v); 
	for (int i=1;i<=n;i++) if (!num[i]) DFS(i);
	for (int i=1;i<=n;i++) for (int j=head[i];j;j=nxt[j])
		if (scc_num[to[j]] != scc_num[i]) in[scc_num[to[j]]]++;
	for (int i=1;i<=scc_cnt;i++) if (!in[i]) vout++; 
	for (int i=1,tag=0;i<=n;i++,tag=0) if (scc_sz[scc_num[i]] == 1 && !in[scc_num[i]]) {
		for (int j=head[i];j;j=nxt[j]) if (in[scc_num[to[j]]] == 1 && scc_num[to[j]] != scc_num[i]) {tag = 1; break;}
		if (!tag) {vout--; break;}
	}
	printf("%.6lf\n",1.0-(double)vout/n);
	return 0;
} 

为了学习仙人掌才来看的这个,然而现在发现仙人掌用的是无向图的TarjanQAQ