Tarjan整理
求强连通分量个数
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
struct sss{
int t, ne;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
e[cnt].t = v;
h[u] = cnt;
}
int dfn[1000005], low[1000005];
int num, su;
bool vis[1000005];
int belog[1000005];
stack<int> s;
int d[1000005];
int sum[1000005];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
vis[x] = true;
s.push(x);
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (!dfn[u]) {
tarjan(u);
low[x] = min(low[x], low[u]);
} else if (vis[u]) {
low[x] = min(low[x], dfn[u]);
}
}
if (dfn[x] == low[x]) {
su++;
int t = 0;
do {
t = s.top();
s.pop();
sum[su]++;
belog[t] = su;
vis[t] = false;
} while(t != x);
}
}
int n, m;
int main() {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
printf("%d", su);
return 0;
}
Tarjan缩点
例题：ATM， 受欢迎的牛；
以前者为例；
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m, st, p;
struct sss{
int t, ne;
}e[1000005], edge[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
int he[1000005], ccnt;
void add_2(int u, int v) {
edge[++ccnt].ne = he[u];
he[u] = ccnt;
edge[ccnt].t = v;
}
vector<int> vec;
bool v[1000005], vis[1000005];
int dfn[1000005], low[1000005];
int a[1000005];
int num, su;
int sum[1000005];
stack<int> s;
int start;
int belog[1000005];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
vis[x] = true;
s.push(x);
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (!dfn[u]) {
tarjan(u);
low[x] = min(low[x], low[u]);
} else if (vis[u]) {
low[x] = min(low[x], dfn[u]);
}
}
if (dfn[x] == low[x]) {
su++;
int t = 0;
do {
t = s.top();
s.pop();
belog[t] = su;
sum[su] += a[t];
vis[t] = false;
if (v[t]) vec.push_back(su);
if (t == st) start = su;
} while(t != x);
}
}
int dis[1000005], vvis[1000005];
void SPFA(int x) {
memset(vvis, 0, sizeof(vvis));
queue<int> q;
vvis[x] = true;
q.push(x);
while(!q.empty()) {
int t = q.front();
q.pop();
vvis[x] = false;
for (int i = he[t]; i; i = edge[i].ne) {
int u = edge[i].t;
if (dis[u] < dis[t] + sum[u]) { //不要吧u写成i！
dis[u] = dis[t] + sum[u];
if (!vvis[u]) {
q.push(u);
vvis[u] = true;
}
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d %d", &st, &p);
for (int i = 1; i <= p; i++) {
scanf("%d", &x);
v[x] = true;
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j; j = e[j].ne) {
int u = e[j].t;
if (belog[i] != belog[u]) {
add_2(belog[i], belog[u]);
}
}
}
for (int i = 1; i <= su; i++) dis[i] = sum[i];
SPFA(start);
int ma = -1;
for (int i = 0; i < vec.size(); i++) {
ma = max(ma, dis[vec[i]]);
}
printf("%d", ma);
return 0;
}
求割点
例题：备用交换机
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int n;
struct sss{
int t, ne;
}e[10000005];
int h[10000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
stack<int> s;
int dfn[1000005], low[1000005];
int d[1000005];
bool vis[1000005], cd[1000005];
int num;
int sum;
int root;
void tarjan(int x) {
dfn[x] = low[x] = ++num;
int son = 0;
s.push(x);
vis[x] = true;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (!dfn[u]) {
son++;
tarjan(u);
low[x] = min(low[x], low[u]);
if (low[u] >= dfn[x]) {
if (x != root || son > 1) cd[x] = true;
}
} else {
low[x] = min(low[x], dfn[u]);
}
}
}
int main() {
scanf("%d", &n);
int x, y;
while(scanf("%d %d", &x, &y) != EOF) {
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
root = i;
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
if (cd[i]) sum++;
}
printf("%d\n", sum);
for (int i = 1; i <= n; i++) {
if (cd[i]) printf("%d\n", i);
}
return 0;
}
求割点与乘法原理的结合
例题：BLO；
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
int n, m;
struct sss{
int t, ne;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
int dfn[1000005], low[1000005];
int num;
stack<int> s;
bool vis[1000005];
long long ans[1000005];
long long sum[1000005];
bool cd[1000005];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
vis[x] = true;
s.push(x);
int son = 0;
sum[x] = 1;
int su = 0;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (!dfn[u]) {
son++;
tarjan(u);
sum[x] += sum[u];
low[x] = min(low[x], low[u]);
if (low[u] >= dfn[x]) {
su += sum[u];
ans[x] += sum[u] * (n - sum[u]);
if (x != 1 || son > 1) {
cd[x] = true;
}
}
} else if (vis[u]) {
low[x] = min(low[x], dfn[u]);
}
}
if (cd[x]) {
ans[x] += (long long)(n - su - 1) * (su + 1) + n - 1;
} else {
ans[x] = (n - 1) << 1;
}
if (dfn[x] == low[x]) {
int t = 0;
do {
t = s.top();
s.pop();
vis[t] = false;
} while(t != x);
}
}
int main() {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
tarjan(1);
for (int i = 1; i <= n; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
求割边
例题：旅游航道；
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int n, m;
struct sss{
int t, ne;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
int dfn[1000005], low[1000005];
int num;
stack<int> s;
int ans;
bool vis[1000005];
bool bri[1000005];
void tarjan(int x, int fa) {
dfn[x] = low[x] = ++num;
vis[x] = true;
s.push(x);
bool first = true;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa && first) {
first = false;
continue;
}
if (!dfn[u]) {
tarjan(u, x);
low[x] = min(low[x], low[u]);
if (low[u] > dfn[x]) {
ans++;
bri[i] = bri[i ^ 1] = true;
}
} else if (vis[u]) {
low[x] = min(low[x], dfn[u]);
}
}
if (dfn[x] == low[x]) {
int t = 0;
do {
t = s.top();
s.pop();
vis[t] = false;
} while(t != x);
}
}
int main() {
scanf("%d %d", &n, &m);
while(n != 0 && m != 0) {
int x, y;
memset(e, 0, sizeof(e));
memset(h, 0, sizeof(h));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(vis, 0, sizeof(vis));
memset(bri, 0, sizeof(bri));
num = 0;
cnt = 0;
ans = 0;
while(!s.empty()) s.pop();
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i, 0);
}
printf("%d\n", ans);
scanf("%d %d", &n, &m);
}
return 0;
}
求边双并重新建没有桥的图
例题：Redundant Paths 分离的路径；
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
int n, m;
struct sss{
int t, ne;
}e[1000005];
int h[1000005], cnt;
void add(int u, int v) {
e[++cnt].ne = h[u];
h[u] = cnt;
e[cnt].t = v;
}
int dfn[1000005], low[1000005];
int num;
int d[1000005];
stack<int> s;
int su;
int belog[1000005];
vector<int> ed[1000005];
void tarjan(int x, int id) {
dfn[x] = low[x] = ++num;
s.push(x);
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (i == (id ^ 1)) continue;
if (!dfn[u]) {
tarjan(u, i);
low[x] = min(low[x], low[u]);
} else {
low[x] = min(low[x], dfn[u]);
}
}
if (dfn[x] == low[x]) {
int t = 0;
su++;
do {
t = s.top();
s.pop();
belog[t] = su;
ed[t].push_back(t);
} while(t != x);
}
}
int main() {
scanf("%d %d", &n, &m);
int x, y;
cnt = 1;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
tarjan(1, 1);
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j; j = e[j].ne) {
int u = e[j].t;
if (belog[i] != belog[u]) {
// d[belog[i]]++;
d[belog[u]]++; //无向边i和u强连通，所以只需加一次，且加哪个都行；
}
}
}
long long ans = 0;
for (int i = 1; i <= su; i++) {
if (d[i] == 1) ans++;
}
printf("%lld", (ans + 1) >> 1);
return 0;
}
求点双
例题：矿场搭建题解；
部分题解及注释待整理；