Tarjan求BCC/割点
然而似乎我一开始抄的白书的板子哪里抄错了？还是本身哪里不对……（可能是不适用于这道题？因为这题要求求出每个BCC的大小。。？
膜拜了ydc的写法= =
其实两次dfs也并没有比lrj的麻烦到哪里去……感觉反而更清晰易懂，不容易出bug
大家都是NOIP之前就会求割点了……只有我比较傻逼……
核心是 $low[son]\geq dfn[fa] \Rightarrow fa 是割点$
嗯如果只有一个BCC那么只需要两个出口，然后如果一个BCC连接着两个（及以上？）割点（这里将两个割点直接相连可以看作是一个BCC？）那么它内部就不用建出口，否则需要建一个……当然方案数直接乘就好啦= =（size[x]，按表示方式不同，可能需要-1减去割点）
/**************************************************************
Problem: 2730
User: Tunix
Language: C++
Result: Accepted
Time:0 ms
Memory:1308 kb
****************************************************************/ //BZOJ 2730
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ struct edge{int x,y,next;}E[N<<],st[N<<];
int n,m,head[N],cnt;
void add(int x,int y){
E[++cnt]=(edge){x,y,head[x]}; head[x]=cnt;
E[++cnt]=(edge){y,x,head[y]}; head[y]=cnt;
}
int dfn[N],low[N],dfs_clock,bccno[N],have[N],size[N],bcc,top;
bool iscut[N]; void tarjan(int x,int fa){
low[x]=dfn[x]=++dfs_clock;
int child=;
for(int i=head[x];i;i=E[i].next){
int y=E[i].y;
if (!dfn[y]){
child++;
tarjan(y,x);
low[x]=min(low[y],low[x]);
if (low[y]>=dfn[x]) iscut[x]=;
}else low[x]=min(low[x],dfn[y]);
}
if (fa< && child==) iscut[x]=;
} bool vis[N];
void dfs(int x){
vis[x]=; size[bcc]++;
for(int i=head[x];i;i=E[i].next)
if (!vis[E[i].y]){
if (!iscut[E[i].y]) dfs(E[i].y);
else if(bccno[E[i].y]!=bcc)
bccno[E[i].y]=bcc,have[bcc]++;
}
}
void Clear(){
CC(head,); CC(bccno,);
CC(dfn,); CC(low,);
CC(have,); CC(size,);
CC(iscut,); CC(vis,);
n=cnt=dfs_clock=bcc=top=;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("2730.in","r",stdin);
freopen("2730.out","w",stdout);
#endif
int cs=;
while(scanf("%d",&m)!=EOF && m){
printf("Case %d: ",++cs);
Clear();
F(i,,m){
int x=getint(),y=getint();
n=max(x,n); n=max(y,n);
add(x,y);
}
F(i,,n) if (!dfn[i]) tarjan(i,-);
LL ans1=,ans2=;
F(i,,n)
if (!vis[i] && !iscut[i]){
++bcc,dfs(i);
if (have[bcc]==) ans1++,ans2*=size[bcc];
}
if (bcc==) ans1=,ans2=(LL)n*(n-)/;
printf("%lld %lld\n",ans1,ans2);
}
return ;
}
2730: [HNOI2012]矿场搭建
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 974 Solved: 458
[Submit][Status][Discuss]
Description
Input
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
Output
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
Sample Input
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Sample Output
Case 2: 4 1