POJ-3352-RoadConstruction（边双联通分量，缩点）

清疚 2022-01-10 05:13 252阅读 0赞

### 链接：[https://vjudge.net/problem/POJ-3352\#author=0][https_vjudge.net_problem_POJ-3352_author_0] ###

### 题意： ###

给一个无向连通图，至少添加几条边使得去掉图中任意一条边不改变图的连通性（即使得它变为边双连通图）。

### 思路： ###

将图中的边双联通分量全部缩成一个点，得到度为1的点的数目。

若要使缩点后的图都边双联通，增加(leaf+1)/2条边即可。leaf就是度为1的点。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <string>
    #include <istream>
    #include <sstream>
    #include <vector>
    #include <stack>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <cstdio>
    #include <set>
    #include <iterator>
    #include <cstring>
    using namespace std;
    
    typedef long long LL;
    const int MAXN = 1e3+10;
    
    vector<int> G[MAXN];
    stack<int> St;
    int Dfn[MAXN], Low[MAXN];
    int Dis[MAXN], Fa[MAXN];
    int times, res, cnt;
    int n, m;
    
    void Init()
    {
        for (int i = 1;i <= n;i++)
            G[i].clear();
        memset(Dfn, 0, sizeof(Dfn));
        memset(Low, 0, sizeof(Low));
        memset(Dis, 0, sizeof(Dis));
        memset(Fa, 0, sizeof(Fa));
        times = res = cnt = 0;
    }
    
    void Tarjan(int u, int v)
    {
        Dfn[v] = Low[v] = ++times;
        St.push(v);
        for (int i = 0;i < G[v].size();i++)
        {
            int node = G[v][i];
            if (node == u)
                continue;
            if (Dfn[node] == 0)
                Tarjan(v, node);
            Low[v] = min(Low[v], Low[node]);
        }
        if (Dfn[v] == Low[v])
        {
            cnt++;
            int node;
            do
            {
                node = St.top();
                Fa[node] = cnt;
                St.pop();
            }
            while (node != v);
        }
    }
    
    int main()
    {
        string s;
        int t;
        while (cin >> n >> m)
        {
            int l, r;
    //        cin >> n >> m;
            Init();
            for (int i = 1;i <= m;i++)
            {
                cin >> l >> r;
                G[l].push_back(r);
                G[r].push_back(l);
            }
            Tarjan(0, 1);
    //        copy(Fa+1, Fa+1+n, ostream_iterator<int> (cout, " "));
    //        copy(Dis+1, Dis+1+n, ostream_iterator<int> (cout, " "));
    //        cout << endl;
            for (int i = 1;i <= n;i++)
            {
                for (int j = 0;j < G[i].size();j++)
                {
                    int node = G[i][j];
                    if (node == i)
                        continue;
                    if (Fa[i] != Fa[node])
                        Dis[Fa[node]]++;
                }
            }
            int leaf = 0;
            for (int i = 1;i <= cnt;i++)
            {
                if (Dis[i] == 1)
                    leaf++;
            }
    //        cout << "Output for Sample Input " << t << endl;
            cout << (leaf+1)/2 << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10857168.html

[https_vjudge.net_problem_POJ-3352_author_0]: https://vjudge.net/problem/POJ-3352#author=0