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

Bertha 。 2022-08-13 15:47 144阅读 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;
    }