图算法和图模型(一)

本篇内容主要写了和dfs有关的算法
比如tarjan算法, kosaraju算法等等
主要围绕图的割顶与桥展开

tarjan算法(无向图)

tarjan01
tarjan02
tarjan03
tarjan04

BZOJ1123

tarjan05

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
const int maxn = 100000 + 10;

class Edge {
public:
int from, to;
Edge(int f = 0, int t = 0) : from(f), to(t) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int dfn[maxn], low[maxn], cut[maxn], size[maxn];
llong ans[maxn];
int clk;
int root;

int n, m;

void init() {
edges.clear();
edges.push_back(Edge());

Set(dfn, 0);
Set(low, 0);
Set(ans, 0);
Set(cut, 0);
Set(size, 0);

clk = 0;
}

void addEdge(int u, int v) {
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
}

void tarjan(int u) {
dfn[u] = low[u] = ++clk;
size[u] = 1;

int cld = 0, sum = 0;

_for(i, 0, G[u].size()) {
int eid = G[u][i];
int v = edges[eid].to;
//debug(v);

if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
size[u] += size[v];

if(low[v] >= dfn[u]) {
cld++;
ans[u] += (llong)(size[v]) * (n - size[v]);
sum += size[v];

if(u != root || cld > 1) cut[u] = 1;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(!cut[u]) ans[u] = 2 * (n - 1);
else {
ans[u] += ((n - 1) + (llong)(n - 1 - sum) * (sum + 1));
}
}

int main() {
freopen("input.txt", "r", stdin);
init();

scanf("%d%d", &n, &m);

_for(i, 0, m) {
int u, v;
scanf("%d%d", &u, &v);
if(u == v) continue;

addEdge(u, v);
addEdge(v, u);
}
// node start from 1

root = 1;
tarjan(root);

_rep(i, 1, n) printf("%lld\n", ans[i]);
}

tarjan无向图的双连通分量

tarjan06
tarjan07
tarjan08

euler路径

tarjan09

POJ2230

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
const int maxn = 100000 + 10;
int n, m;
int st;
vector<int> G[maxn];
int head[maxn];
stack<int> stk;
vector<int> ans;

struct Edge {
int u, v;
Edge(int u = 0, int v = 0) : u(u), v(v) {}
};

vector<Edge> edges;

void init() {
_for(i, 0, maxn) G[i].clear();
while(!stk.empty()) stk.pop();
edges.push_back(Edge());
edges.push_back(Edge());
Set(head, 0);
ans.clear();
}

void addEdge(int u, int v) {
edges.push_back(Edge(u, v));
G[u].push_back(edges.size() - 1);
}

void euler() {
stk.push(st);
while (!stk.empty()) {
int x = stk.top(), i = head[x];
// debug(x);

if(i < G[x].size()) {
int eid = G[x][i];
int y = edges[eid].v;

stk.push(y);
head[x] = i + 1;
}
else {
stk.pop();
ans.push_back(x);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

_rep(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}

st = 1;
euler();
for(int i = ans.size() - 1; i >= 0; i--) printf("%d\n", ans[i]);
}

tarjan算法(有向图)

tarjan10

tarjan有向图的强连通分量

tarjan11
tarjan12
tarjan13

树的直径

BZOJ1912
BZOJ1912.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
const int maxn = 100000 + 10;

class Edge {
public:
int to, weight;
Edge(int t = 0, int w = 0) : to(t), weight(w) {}
};

vector<Edge> edges;
vector<int> G[maxn];
int n, k;
int pa[maxn * 2], d[maxn * 2], vis[maxn * 2];

void init() {
edges.push_back(Edge());
edges.push_back(Edge());

_for(i, 0, maxn) G[i].clear();
Set(pa, 0);
Set(d, 0);
Set(vis, 0);
}

void addEdge(int from, int to, int w) {
edges.push_back(Edge(to, w));
G[from].push_back(edges.size() - 1);
}

void dfs(int u, int& to) {
vis[u] = 1;

_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(vis[v]) continue;
if((d[v] = d[u] + edges[eid].weight) >= d[to]) to = v;
pa[v] = eid;

dfs(v, to);
}

vis[u] = 0;
}

void dp(int u, int& ans) {
vis[u] = 1;
_for(i, 0, G[u].size()) {
int eid = G[u][i], v = edges[eid].to;

if(vis[v]) continue;
dp(v, ans);

ans = max(ans, d[u] + d[v] + edges[eid].weight);
d[u] = max(d[u], d[v] + edges[eid].weight);
}
}

int main() {
freopen("input.txt", "r", stdin);

init();
scanf("%d%d", &n, &k);
_for(i, 0, n) {
int u, v;
scanf("%d%d", &u, &v);

addEdge(u, v, 1);
addEdge(v, u, 1);
}

// then solve the problem
int to = 1;
dfs(1, to);

d[to] = pa[to] = 0;
int tto = to;
dfs(to, tto);
// [to, tto] is the longest path in a tree

int ans = ((n - 1) << 1) - d[tto] + 1;

if(k == 2) {
while (pa[tto]) {
int eid = pa[tto];
edges[eid].weight = edges[eid ^ 1].weight = -1;
tto = edges[eid ^ 1].to;
}

tto = 0;
Set(d, 0);
Set(vis, 0);
dp(to, tto);
ans -= (tto - 1);
}

printf("%d\n", ans);
}

tarjan算法实践