【UVALive】5135 Mining Your Own Business 点双连通+割顶

传送门：【UVALive】5135 Mining Your Own Business

题目分析：首先我们可以轻易确定救援出口设置在割顶上一定不是最优的，同时如果一个点双连通分量内有多个割顶则不需要设置救援出口，只有当该分量内割顶数为1时该分量内才需要设置救援出口。于是我们只要求每个点双连通分量内点的个数以及割点就好，ans2等于所有只有一个割顶的分量内元素个数-1的乘积。对于无割顶的图ans1=2，ans2=V*（V-1）/2。

PS：本算法将叶子节点默认和一个割顶算作一个连通分量，这样可以便于求解。

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#definerep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 100005 ;
const int MAXE = 1000005 ;

struct Edge {
int v , n ;
Edge () {}
Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;

Edge E[MAXE] ;
int H[MAXN] , bcc[MAXN] , cntE ;
int dfn[MAXN] , low[MAXN] ;
int S[MAXN] , top ;
int iscut[MAXN] ;
int size[MAXN] ;
int dfs_clock ;
int bcc_cnt ;
int n ;

void clear () {
top = 0 ;
cntE = 0 ;
bcc_cnt = 0 ;
dfs_clock = 0 ;
clr ( H , -1 ) ;
clr ( dfn , 0 ) ;
clr ( size , 0 ) ;
clr ( bcc , -1 ) ;
clr ( iscut , 0 ) ;
}

void addedge ( int u , int v , int H[] ) {
E[cntE] = Edge ( v , H[u] ) ;
H[u] = cntE ++ ;
}

void tarjan ( int u , int fa ) {
dfn[u] = low[u] = ++ dfs_clock ;
S[top ++] = u ;
int son = 0 ;
for ( int i = H[u] ; ~i ; i = E[i].n ) {
int v = E[i].v ;
if ( !dfn[v] ) {
++ son ;
tarjan ( v , u ) ;
low[u] = min ( low[u] , low[v] ) ;
if ( low[v] >= dfn[u] ) {
iscut[u] = 1 ;
++ bcc_cnt ;
while ( 1 ) {
++ size[bcc_cnt] ;
int x = S[-- top] ;
addedge ( bcc_cnt , x , bcc ) ;
if ( x == v ) break ;
}
++ size[bcc_cnt] ;
addedge ( bcc_cnt , u , bcc ) ;
}
} else if ( v != fa ) low[u] = min ( low[u] , dfn[v] ) ;
}
if ( fa < 0 && son == 1 ) iscut[u] = 0 ;
}

void solve () {
int u , v ;
LL ans1 = 0 , ans2 = 1 ;
clear () ;
int maxnode = 0 ;
rep ( i , 0 , n ) {
scanf ( "%d%d" , &u , &v ) ;
addedge ( u , v , H ) ;
addedge ( v , u , H ) ;
maxnode = max ( maxnode , u ) ;
maxnode = max ( maxnode , v ) ; 
}
For ( i , 1 , maxnode ) if ( !dfn[i] ) tarjan ( i , -1 ) ;
For ( u , 1 , bcc_cnt ) {
int cnt = 0 ;
for ( int i = bcc[u] ; ~i ; i = E[i].n ) {
int v = E[i].v ;
if ( iscut[v] ) ++ cnt ;
//printf ( "%d %d\n" , u , v ) ;
}
if ( cnt == 1 ) {
++ ans1 ;
ans2 *= size[u] - 1 ;
}
}
if ( bcc_cnt == 1 ) {
ans1 = 2 ;
ans2 = ( LL ) size[1] * ( size[1] - 1 ) / 2 ;
}
printf ( "%lld %lld\n" , ans1 , ans2 ) ;
}

int main () {
int cas = 0 ;
while ( ~scanf ( "%d" , &n ) && n ) {
printf ( "Case %d: " , ++ cas ) ;
solve () ;
}
return 0 ;
}