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

链接：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;

}

巴特西

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

链接：https://vjudge.net/problem/POJ-3352#author=0

题意：

思路：

代码：

最新文章

热门文章