图的割边求法汇总(基准, 并查集, Tarjan算法)及代码实现


求图的割边的三种方法

  • 基准算法
  • 并查集算法
  • Tarjan算法

基准与并查集算法都是暴力做法, 并查集算法只是对求连通块个数算法做了优化(将时间复杂度由O(n^3)降到了O(n^2)), 思路都是删边之后求一遍连通块个数, 然后与没删边的连通块个数比较, 若增加了即为桥, 否则不为桥

基准算法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e7 + 10, M = 2e7 + 10;

int n, m, ans, cnt_1, cnt_2;
int h[N], e[M], ne[M], idx;
bool used[M], vis[N];
int q[N];

void add (int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool bfs (int x)
{
    int hh = 0, tt = 0;
    q[0] = x;
    vis[x] = 1;

    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t] ; ~i ; i = ne[i])
        {
            if(used[i]) continue;
            int j = e[i];
            if(!vis[j])
            {
                vis[j] = 1;
                q[++ tt] = j;
            }
        }
    }
}

void check ()
{
    for(int i = 0 ; i < n ; i ++ )
        for(int j = h[i] ; ~j ; j = ne[j])
        {
            memset(vis, 0, sizeof vis);
            cnt_2 = 0;
            used[j] = used[j ^ 1] = 1;
            for(int k = 0 ; k < n ; k ++ )
                if(!vis[k])
                {
                    bfs(k);
                    cnt_2 ++ ;
                }

            if(cnt_1 < cnt_2) ans ++ ;
            used[j ^ 1] = used[j] = 0;
        }
}

int main () {
    cin >> n >> m;

    memset(h, -1, sizeof h);
    while (m--) 
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    for (int i = 0; i < n; i++)
        if (!vis[i])
        {
            bfs(i);
            cnt_1++;
        }                                                        

    check();

    cout << ans / 2 << endl;

    return 0;
}

并查集算法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e6 + 10, M = 2e7 + 10;

int n, m, ans, cnt_1, cnt_2;
int h[N], e[M], ne[M], idx;
bool used[M];
int p[N], np[N]; // 新并查集数组
vector<int> a;

void add (int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int find (int x, int y[])
{
    if(y[x] != x) y[x] = find(y[x], y);
    return y[x];
}

int cal (int s[])
{

    a.clear();
    for(int i = 0 ; i < n ; i ++ )
    {
        int flag = 1, pp = find(i, s);
        for(int j = 0 ; j < a.size() ; j ++ )
        {
            if(pp == a[j]) 
            {
                flag = 0;
                break;
            }
            if(flag) a.push_back(pp);
        }
    }

    return a.size();
}

void f ()
{
    for(int i = 0 ; i < n ; i ++ ) np[i] = i;
    for(int i = 0 ; i < n ; i ++ )
        for(int j = h[i] ; ~j ; j = ne[j])
        {
            if(used[j]) continue;

            int k = e[j];
            int npi = find(i, np), npk = find(k, np);
            np[npi] = npk;
        }
}

void check ()
{
    for(int i = 0 ; i < n ; i ++ )
        for(int j = h[i] ; ~j ; j = ne[j])
        {
            used[j] = used[j ^ 1] = 1;

            f();

            cnt_2 = cal(np);

            used[j] = used[j ^ 1] = 0;                                                                                    

            if(cnt_1 < cnt_2) ans ++ ;
        }                                                                        
}

int main ()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    for(int i = 0 ; i < n ; i ++ ) p[i] = i;
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
        int pa = find(a, p), pb = find(b, p);
        p[pa] = pb;
    }

    cnt_1 = cal(p);

    check();

    cout << ans / 2 << endl;

    return 0;
}

Tarjan算法

Portal


评论
 Previous
网络最大流与最小截问题 -- EK算法详解 网络最大流与最小截问题 -- EK算法详解
解决问题对于一张图, 我们对于每条边有两个特性, 单位时间能传输的最大流量(容量)和流量, 流量必须小于等于容量并且对于每个点来说, 流入的流量和与流出的流量和必须相等. 最大流算法就是解决图中一个点到另一个点的单位时间内能传输的最大流量.
2020-07-02
Next 
2019安徽-省赛J题 密信 2019安徽-省赛J题 密信
If you want to read this article, please go to About page, scan wechat or alipay QR code, pay 200 yuan and contact blogger through QQ, then you can get the passsword and read the article.
  TOC