POJ1144 Network 无向图的割顶

现在打算重新学习图论的一些基础算法,包括像桥,割顶,双连通分量,强连通分量这些基础算法我都打算重敲一次,因为这些量都是可以用tarjan的算法求得的,这次的割顶算是对tarjan的那一类算法的理解的再次实现吧,后面打算做一下桥的判断和边双连通的关系,边双连通处理的时候如果又重边的话会很不一样,割顶也会相应的不一样,这里的代码是没有考虑重边的,后面再写一个考虑重边的吧。

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
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#define maxn 150
using namespace std;
 
vector<int> G[maxn];
int n;
int low[maxn], pre[maxn];
int dfs_clock;
bool iscut[maxn];
 
int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock; int ch = 0;
    for (int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if (!pre[v]){
            ch++;
            int lowv=dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= pre[u]){
                iscut[u] = true;
                //if (lowv>pre[u]) (u,v)是桥
            }
        }
        else if (pre[v] < pre[u] && v != fa){
            lowu = min(lowu, pre[v]);
        }
    }
    if (fa < 0 && ch == 1) iscut[u] = false;
    return low[u] = lowu;
}
 
void init()
{
    memset(low, 0, sizeof(low));
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    dfs_clock = 0;
    for (int i = 1; i <= n; i++){
        if (!pre[i]) dfs(i, -1);
    }
}
 
int main()
{
    while (cin >> n&&n)
    {
        for (int i = 0; i <= n; i++) G[i].clear();
        int a,b; char c;
        while (scanf("%d", &a)==1&&a){
            while ((c = getchar()) != ‘\n‘){
                scanf("%d", &b);
                G[a].push_back(b);
                G[b].push_back(a);
            }
        }
        init(); int ans = 0;
        for (int i = 1; i <= n; i++){
            if (iscut[i]) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

POJ1144 Network 无向图的割顶

上一篇:php随笔4-基本复习-Ajax


下一篇:ASP.NET MVC 视图