poj 3177 & 3352 【无向图双连通分量Tarjan】-蒲公英云

poj 3177 & 3352 【无向图双连通分量Tarjan】

Bertha 。 2022-08-13 15:47 240阅读 0赞

题目：poj 3177 & 3352

题意：大概意思就是给你一个无向图，让你添加最少的边，让所有点都双连通。

分析：双连通的定义就是任意两个点至少有两条路可达。

其实做法跟添加最少边强连通一样，先对图中已经双连通的缩点，然后重新编号。

这就是著名的Tanjan算法。

通过搜索的思想对所有存在环的边遍相同的号

如果要让所有的点双连通，那么对于缩点后的图中如果度数为 1 的话，这些边肯定要连接到其他的点才能双连通，而题目要求添加最少，所以连接到其他度数也为 1 的点是最优的，那么答案就是（odd+1）/ 2

注意：图中存在重边，所以要判重。

AC代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 1100;
const int inf = 0x3f3f3f3f;
int vis[N],dfn[N],low[N];
vector<int> v[N];
struct Node
{
    int from,to;
};
int bcc_cnt;
stack<Node> s;
void add_Node(int x,int y)
{
    v[x].push_back(y);
    v[y].push_back(x);
}
void Tarjan(int u,int fa)
{
    vis[u]=1;
    dfn[u]=low[u]=++bcc_cnt;
    for(int i=0;i<v[u].size();i++)
    {
        int to=v[u][i];
        if(vis[to]==1 && to!=fa) //假如与其联通的点访问过了
            low[u]=min(low[u],dfn[to]);
        if(!vis[to])
        {
            Tarjan(to,u);
            low[u]=min(low[u],low[to]);
        }
    }
    vis[u]=2;
}
int in[N];
int Yougth(int n)
{
    Del(in,0);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<v[i].size(); j++)
        {
            int to = v[i][j];
            //printf("%d %d %d %d\n",i+1,to+1,low[i],low[to]);
            if(low[i]!=low[to])
            {
                in[low[i]]++;
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=bcc_cnt;i++)
        if(in[i]==1)
            ans++;
    return (ans+1)/2;
}
void Clear(int x)
{
    for(int i=0;i<x;i++)
        v[i].clear();
}
int main()
{
    //freopen("Input.txt","r",stdin);
    int n,m;
    string s1,s2,cas;
    while(cin>>s1>>s2>>cas)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int ok = 0;
            for(int j=0;j<v[x-1].size();j++)
                if(v[x-1][j]==(y-1)){
                    ok = 1;
                    break;
                }
            if(ok)
                continue;
            add_Node(x-1,y-1);
        }
        cout<<"Output for "<<s1<<" "<<s2<<" "<<cas<<endl;
        Del(vis,0),Del(dfn,0),Del(low,0);
        bcc_cnt = 0;
        Tarjan(0,1);
        printf("%d\n\n",Yougth(n));
        Clear(n);
    }
    return 0;
}