训练指南 UVALive - 5135 （双连通分量）

layout: post

title: 训练指南 UVALive - 5135 （双连通分量）

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 双连通分量

- 图论

- 训练指南

Mining Your Own Business

UVALive - 5135

题意

在一张无向图中，将一些点涂上黑色，使得删掉图中任何一个点时，每个连通分量至少有一个黑点。问最少能涂几个黑点，并且在涂最少的情况下有几种方案。

显然，一定不能涂割点。对于每一个连通分量，如果有1个割点，则必须涂上分量内除割点之外的任意一个点，如果有多个（2个及以上）割点，则这个分量不需要涂色。如果整张图都没有割点，那么任选两个点涂色即可，之所以要涂两个，是要防止删掉的电恰是黑点的情况。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=998244353;

const int maxn=1e6+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

struct Edge{

    int u,v;

};

///割顶 bccno 无意义

int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cut;

vector<int>G[maxn],bcc[maxn];

stack<Edge>S;

int dfs(int u,int fa){

    int lowu = pre[u] = ++dfs_clock;

    int child = 0;

    for(int i = 0; i < G[u].size(); i++){

        int v =G[u][i];

        Edge e = (Edge){u,v};

        if(!pre[v]){ ///没有访问过

            S.push(e);

            child++;

            int lowv = dfs(v, u);

            lowu=min(lowu, lowv);                ///用后代更新

            if(lowv >= pre[u]){

                iscut[u]=true;

                bcc_cut++;bcc[bcc_cut].clear();   ///注意 bcc从1开始

                for(;;){

                    Edge x=S.top();S.pop();

                    if(bccno[x.u] != bcc_cut){bcc[bcc_cut].push_back(x.u);bccno[x.u]=bcc_cut;}

                    if(bccno[x.v] != bcc_cut){bcc[bcc_cut].push_back(x.v);bccno[x.v]=bcc_cut;}

                    if(x.u==u&&x.v==v)break;

                }

            }

        }

        else if(pre[v] < pre[u] && v !=fa){

            S.push(e);

            lowu = min(lowu,pre[v]);

        }

    }

    if(fa < 0 && child == 1) iscut[u] = 0;

    return lowu;

}

void find_bcc(int n){

    memset(pre, 0, sizeof(pre));

    memset(iscut, 0, sizeof(iscut));

    memset(bccno, 0, sizeof(bccno));

    dfs_clock = bcc_cut = 0;

    for(int i = 0; i < n;i++)

        if(!pre[i])dfs(i,-1);

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n,Case=1;

    int mx;

    while(cin>>n&&n){

        for(int i=0;i<2*n;i++)G[i].clear();

        mx=-inf;

        for(int i=0;i<n;i++){

            int u,v;

            cin>>u>>v;mx=max(mx,max(u,v));

            u--,v--;

            G[u].push_back(v);

            G[v].push_back(u);

        }

        find_bcc(mx);

        ll ans1=0,ans2=1;

        for(int i=1;i<=bcc_cut;i++){

            int cut_cnt=0;

            for(int j=0;j<bcc[i].size();j++)

                if(iscut[bcc[i][j]])cut_cnt++;

            if(cut_cnt==1){

                ans1++;

                ans2*=(ll)(bcc[i].size()-cut_cnt);

            }

        }

        if(bcc_cut==1){

            ans1=2;

            ans2=ll(bcc[1].size()*(bcc[1].size()*1LL-1LL)/2LL);

        }

        cout<<"Case "<<Case++<<": "<<ans1<<" "<<ans2<<endl;

    }

    return 0;

}

巴特西

训练指南 UVALive - 5135 （双连通分量）

Mining Your Own Business

题意

最新文章

热门文章