【算法笔记】Kosaraju算法

前言

$T1$就是$Claris$用$bitset$配合这个算法把求$SCC$优化到了$\frac{n^2}{32}$

算法概述

$step \ 1.$ DFS一遍，记录下后序遍历的顺序
$step \ 2.$ 沿后续遍历的逆序、沿反向边再DFS一遍，每一个连通块即为一个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]);
}
}
}


【日常小测】友好城市

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] 杀人游戏

PS:此题的随机数据不容易拍出错QAQ

#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;
}