tarjan求割点与割边

时间：2020-12-28 02:36:31

tarjan求割点与割边

洛谷P3388 【模板】割点（割顶）

割点

解题思路：

求割点和割点数量模版，对于(u,v)如果low[v]>=dfn[u]那么u为割点,特判根结点，若根结点子树有超过一颗子树，说明根也是割点

#include<bits/stdc++.h>

using namespace std;

/*    freopen("k.in", "r", stdin);

    freopen("k.out", "w", stdout); */

//clock_t c1 = clock();

//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define de(a) cout << #a << " = " << a << endl

#define rep(i, a, n) for (int i = a; i <= n; i++)

#define per(i, a, n) for (int i = n; i >= a; i--)

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

typedef vector<int, int> VII;

#define inf 0x3f3f3f3f

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MAXN = 5e5 + 7;

const ll MAXM = 1e6 + 7;

const ll MOD = 1e9 + 7;

const double eps = 1e-6;

const double pi = acos(-1.0);

int n, m;

int head[MAXN];

struct Edge

{

    int u, v, Next;

    Edge(int _u = 0, int _v = 0, int _Next = 0) { u = _u, v = _v, Next = _Next; }

} e[MAXN];

int cnt = -1;

void add(int u, int v)

{

    e[++cnt].u = u;

    e[cnt].v = v;

    e[cnt].Next = head[u];

    head[u] = cnt;

}

int dfn[MAXN], low[MAXN], dep;

int cut[MAXN];

//对于(u,v)如果low[v]>=dfn[u]那么u为割点,特判根结点，若根结点子树有超过一颗子树，说明根也是割点

void tarjan(int now, int fa)

{

    dfn[now] = low[now] = ++dep;

    int child = 0;

    for (int i = head[now]; ~i; i = e[i].Next)

    {

        int v = e[i].v;

        if (!dfn[v])

        {

            tarjan(v, fa);

            low[now] = min(low[now], low[v]);

            if (low[v] >= dfn[now] && now != fa)

                cut[now]=1;

            if (now == fa)

                child++;

        }

        low[now] = min(low[now], dfn[v]);

    }

    if (child >= 2 && now == fa)

        cut[now] = 1;

}

int main()

{

    memset(head, -1, sizeof(head));

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

    for (int i = 0; i < m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        add(u, v);

        add(v, u);

    }

    for (int i = 1; i <= n; i++)

        if (!dfn[i])

            tarjan(i, i);

    int ans = 0;

    for (int i = 1; i <= n; i++)

        if (cut[i])

            ans++;

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

    for (int i = 1; i <= n; i++)

        if (cut[i])

            printf("%d ", i);

    printf("\n");

    return 0;

}

HDU-4738 Caocao's Bridges

割边

解题思路：

裸的割边，但是有三个坑点

一：如果图不连通，不用派人去炸桥，直接输出0

二：可能会有重边

三：如果桥上没有士兵守着，那至少要派一个人去炸桥。

#include <bits/stdc++.h>

using namespace std;

/*    freopen("k.in", "r", stdin);

    freopen("k.out", "w", stdout); */

//clock_t c1 = clock();

//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define de(a) cout << #a << " = " << a << endl

#define rep(i, a, n) for (int i = a; i <= n; i++)

#define per(i, a, n) for (int i = n; i >= a; i--)

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

typedef vector<int, int> VII;

#define inf 0x3f3f3f3f

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MAXN = 5e5 + 7;

const ll MAXM = 1e6 + 7;

const ll MOD = 1e9 + 7;

const double eps = 1e-6;

const double pi = acos(-1.0);

int n, m;

int head[MAXN];

struct Edge

{

    int u, v, val, Next, flag;

    Edge(int _u = 0, int _v = 0, int _val = 0, int _Next = 0, int _flag = 0) { u = _u, v = _v, v = _val, Next = _Next, flag = _flag; }

} e[MAXN << 1];

int cnt = -1;

void add(int u, int v, int val)

{

    e[++cnt].u = u;

    e[cnt].flag = 0;

    e[cnt].val = val;

    e[cnt].v = v;

    e[cnt].Next = head[u];

    head[u] = cnt;

}

int dfn[MAXN], low[MAXN], dep;

int cut[MAXN << 1];

//如果(u,v)是割边，当且仅当其满足low[v]>dfn[u]

int ans = inf;

void tarjan(int now, int fa)

{

    dfn[now] = low[now] = ++dep;

    int flag = true;

    for (int i = head[now]; ~i; i = e[i].Next)

    {

        int v = e[i].v;

        if (flag && v == fa)

        {

            flag = false;

            continue;

        }

        if (!dfn[v])

        {

            tarjan(v, now);

            low[now] = min(low[now], low[v]);

            if (low[v] > dfn[now])

                e[i].flag = e[i ^ 1].flag = 1;

        }

        low[now] = min(low[now], dfn[v]);

    }

}

void init()

{

    cnt = -1, dep = 0, ans = inf;

    memset(dfn, 0, sizeof(dfn));

    memset(low, 0, sizeof(low));

    memset(cut, 0, sizeof(cut));

    memset(head, -1, sizeof(head));

}

int main()

{

    while (~scanf("%d%d", &n, &m) && n && m)

    {

        init();

        for (int i = 0; i < m; i++)

        {

            int u, v, w;

            scanf("%d%d%d", &u, &v, &w);

            add(u, v, w);

            add(v, u, w);

        }

        int k = 0;

        for (int i = 1; i <= n; i++)

            if (!dfn[i])

                tarjan(i, -1), k++;

        if (k > 1)

            printf("0\n");

        else

        {

            for (int i = 0; i < cnt; i++)

                if (e[i].flag)

                    ans = min(ans, e[i].val);

            if (ans == inf)

                ans = -1;

            else if (ans == 0)

                ans = 1;

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

        }

    }

    return 0;

}

相关文章