UVA-10765 - Doves and bombs(点双连通度)

 

题意:给定一个n个点的连通的无向图，一个点的“鸽子值”定义为将它从图中删去后连通块的个数。求每个点的“鸽子值”。

分析:对于点u,若u不是割顶,则删去后图还是连通的,所以鸽子值是1,若u是割顶,则鸽子值就是它周围相连的bcc个数.

// File Name: 10765.cpp
// Author: Zlbing
// Created Time: 2013/4/15 13:24:10

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=1e4+100;
struct Edge{
    int u,v;
};
vector<int>G[MAXN],bcc[MAXN];
int pre[MAXN],iscut[MAXN],bccno[MAXN],dfs_clock,bcc_cnt;
// 割顶的bccno无意义
stack<Edge> S;
int n,m;
struct node{
    int pos,val;
    bool operator <(const node& a)const{
        if(val==a.val)
            return pos<a.pos;
        else return val>a.val;
    }
}T[MAXN];
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;
        e.u=u,e.v=v;
        if(!pre[v])
        {
            S.push(e);
            child++;
            int lowv=dfs(v,u);
            lowu=min(lowu,lowv);
            if(lowv>=pre[u])
            {
                iscut[u]=1;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                for(;;)
                {
                    Edge x=S.top();S.pop();
                    if(bccno[x.u]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u]=bcc_cnt;
                    }
                    if(bccno[x.v]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v]=bcc_cnt;
                    }
                    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;
}
set<int> ss;
void find_bcc()
{
    memset(pre,0,sizeof(pre));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    dfs_clock=bcc_cnt=0;
    ss.clear();
    for(int i=0;i<n;i++)
        if(!pre[i])dfs(2,-1);
    REP(i,0,n-1)
        if(iscut[i])
        {
            for(int j=0;j<G[i].size();j++)
            {
                int v=G[i][j];
                ss.insert(bccno[v]);
            }
            T[i].pos=i;
            T[i].val=ss.size();
            ss.clear();
        }
        else {
            T[i].pos=i;
            T[i].val=1;
        }
    sort(T,T+n);
    REP(i,0,m-1)
        printf("%d %d\n",T[i].pos,T[i].val);
    printf("\n");
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)break;
        int a,b;
        REP(i,0,n-1){
            G[i].clear();
        }
        while(true)
        {
            scanf("%d%d",&a,&b);
            if(a==-1&&b==-1)break;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        find_bcc();
    }
    return 0;
}