求强连通分量个数
#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缩点
以前者为例；
#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;
}