data-structure-and-algorithm/articulation_point.cpp at master · ywen-cmd/data-structure-and-algorithm · GitHub

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
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

#define PRINT_ARRAY(a,n)    do{for(int i = 0; i < n; i++) cout<<a[i]<<"|"; cout<<endl;}while(0)

/**********************************************
    无向图的割点&桥 Tarjan算法

**********************************************/

/**********************************************
    1 - 0 -3
    | /    |
    2      4

    割点case1 :0,3
    桥 0-3 3-4
**********************************************/
// #define V (5)
// int g[V][V] =
// { // 0 1 2 3 4
//     {0,1,1,1,0},
//     {1,0,1,0,0},
//     {1,1,0,0,0},
//     {1,0,0,0,1},
//     {0,0,0,1,0},
// };

/**********************************************
    0 - 1   6  7
    | / |   | /|
    2 - 3 - 4  5

    割点 3,4,7
    桥 3-4 4-7 7-5 4-6
**********************************************/
#define V (8)
int g[V][V] =
{ // 0 1 2 3 4 5 6 7
    {0,1,1,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {1,1,0,1,0,0,0,0},
    {0,1,1,0,1,0,0,0},
    {0,0,0,1,0,0,1,1},
    {0,0,0,0,0,0,0,1},
    {0,0,0,0,1,0,0,0},
    {0,0,0,0,1,1,0,0},
};

void tarjan_dfs(int x, int dfn[], int low[], int fa[], bool ap[])
{
    static int times = 1;
    dfn[x] = low[x] = times++;
    int child = 0;
    for(int y = 0; y < V; y++)
    {
        if(g[x][y])
        {
            if(0 == dfn[y])
            {
                child++;
                fa[y] = x;
                tarjan_dfs(y, dfn, low, fa, ap);

                if((-1 == fa[x] && child > 1)
                || (-1 != fa[x] && dfn[x] <= low[y]))
                    ap[x] = true;
                if(dfn[x] < low[y])
                    cout<<x<<"->"<<y<<" is bridge"<<endl;

                low[x] = min(low[x], low[y]);
            }
            else if(y != fa[x])
                low[x] = min(low[x], dfn[y]);
            }
    }
}

void articulation_point()
{
    bool ap[V];
    int dfn[V], low[V], fa[V];

    bzero(ap, sizeof(ap));
    bzero(dfn, sizeof(dfn));
    bzero(low, sizeof(dfn));
    memset(fa, -1, sizeof(fa));

    for(int i = 0; i < V; i++)
        if(!dfn[i])
            tarjan_dfs(i, dfn, low, fa, ap);

    for(int i = 0; i < V; i++)
        if(ap[i])
            if(-1 == fa[i]) cout<<"cut point ["<<i<<"] : root"<<endl;
            else            cout<<"cut point ["<<i<<"] : not root"<<endl;

    PRINT_ARRAY(fa, V);
    PRINT_ARRAY(low, V);
}

int main()
{
    articulation_point();

    return 0;
}