算法竞赛进阶指南 0x21 树与图的遍历

这算是总结性的文章，比较简略，不太适合初学者

深度优先搜索

//所有的有向边经过一次（无向边经过两次）
void dfs(int x)
{
    v[x] = true;
    for(int i = head[x]; i; i = nxt[x])
    {
        int y = ver[i];
        if(v[y]) continue;
        dfs(y);
    }
}
//main
dfs(1);
1
2
3
4
5
6
7
8
9
10
11
12
13

可以使用num, dfn[]构建时间戳

树的DFS序

在进入某一个节点以及离开这一个节点进行回溯的时候，记录一次编号，得到长度为2*N的序列。

//所有的有向边经过一次（无向边经过两次）
void dfs(int x)
{
    a[++m] = x;
    v[x] = true;
    for(int i = head[x]; i; i = nxt[x])
    {
        int y = ver[i];
        if(v[y]) continue;
        dfs(y);
    }
    a[++m] = x;
}
//main
dfs(1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

作用：把子树的统计转化为对应的区间上的统计。

树的深度

（树的根节点的深度为 0 ）

在dfs的时候，直接加上d[y] = d[x] + 1

树的子树的大小

使用size[]来进行表示

叶子节点的为1，其他节点的为所有儿子的seze和加一。

树的重心

设max_part(x)是删去 x 点之后，剩下的子树中的最大的一棵。

树的重心的求法：

int ans;
int p;
int size[N];
void dfs(int x)
{
    size[x] = 1;
    int max_part = 0;
    v[x] = true;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(v[y]) continue;
        dfs(y);
        size[x] += size[y];
        max_part = max(max_part, size[y]);
    }  
    max_part = max(max_part, n - size[x]);
    if(max_part < ans)
    {
        p = x;
        ans = max_part;
    }
}

//main
	max = 0x3f3f3f3f;
	dfs(1);
	cout << p << "\n";
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

连通块的遍历

int c[N];
int cnt;
void dfs(int x)
{
    c[x] = cnt;
    v[x] = true;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(v[y]) continue;
        dfs(y);

    }
}
//main
{
    for(int i = 1; i <= n; i++) {
        if(!v[i])
        {
            cnt++;
            dfs(i);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

值得注意：其实v[]数组没有什么作用，因为c[]数组就可以代替他的作用。

图以及树的广度优先遍历

广度优先是一种按照层次来进行访问的遍历方法！！

在遍历的过程中，会得到一个d[]数组，这一个数组中，表示从起点走到这一个点所需要经过的最小点数。

queue<int> q;
void bfs(int s)
{
    v[s] = true;
    q.push(s);
    d[s] = 1;
    while(q.size())
    {
        int x = q.front(); q.pop();
        for(int  i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            if(v[y]) continue;
            v[y] = true;
            q.push(y);
            d[y] = d[x] + 1;
        }
    }
}
//注意：根节点的层次为1
//其实v数组也是多余的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

广度优先遍历的特征

1. 满足两段性以及单调性
   两段性：最多有两个层次的节点（一个是i层，另一个是 i+1层）
   单调性：i 层的在 i+1 层的后面
2. 仅仅在访问完i层以后才访问 i+1 层

拓扑排序

拓扑排序可以进行检查图中有没有环

拓扑排序的板子：

#include
using namespace std;
#define N 305
#define M 305
int n, m;
int head[N], tot, ver[M], nxt[M];
int deg[N];
int a[N], cnt;
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    deg[y] ++;
}

void topsort()
{
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        if(deg[i] == 0) q.push(i);
    }
    while(q.size())
    {
        int x = q.front();
        q.pop();
        a[++cnt] = x;
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            deg[y] --;
            if(deg[y] == 0) q.push(y);
        }
    }
}

int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }

    topsort();

    for(int i = 1; i <= cnt; i++)
    {
        printf("%d  ", a[i]);
    }
    return 0;
}
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

AcWing164. 可达性统

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式

第一行两个整数 N,M，

接下来 M 行每行两个整数 x,y，表示从 x 到 y 的一条有向边。

输出格式

输出共 N 行，表示每个点能够到达的点的数量。

数据范围

1≤N,M≤30000

输入样例：

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
1
2
3
4
5
6
7
8
9
10
11

输出样例：

1
6
3
3
2
1
1
1
1
1
1
2
3
4
5
6
7
8
9
10

在这里求解并集并没有什么好的办法，这里使用了baoli

采用bitset的或运算来求并集，比较离谱。

时间复杂度为：$\frac{N(N+M)}{32}$

#include
using namespace std;
#define N 30005
#define M 30005
int n, m;
int head[N], tot, ver[M], nxt[M];
int deg[N];
bitset<N> bit[N];
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    deg[y] ++;
}

void topsort()
{
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        if(deg[i] == 0) q.push(i);
    }
    while(q.size())
    {
      
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            bit[y] |= bit[x];
            deg[y] --;
            if(deg[y] == 0) q.push(y);
        }
    }
}

int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(y, x);//建立一张反图
    }
    for(int i = 1; i <= n; i++) bit[i][i] = 1;
    topsort();

    for(int i = 1; i <= n; i++)
    {
        printf("%d\n", bit[i].count());
    }
    return 0;
}
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