题目描述
样例
输入
9
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
输出
Case 1: 2 4
Case 2: 4 1
法一（点双）
考虑每一个vDCC，每个割点可以看成不同连通块间的通道，如果没被砸，能通过这个割点跑到其他连通块中。
- 情况一
如果一个vDCC中没有割点，需要两个安全通道（防止其中一个被砸）。
- 情况二
有一个割点，割点一定建，除此之外每个vDCC还要建一个，防止割点被砸。
- 情况三
有两个割点，不用建，一个塌了走另外一个去其他vDCC。
- 综上
所以求vDCC时顺便记录割点数量，分情况。
方案数：\(sum\)，安全通道数：\(cnt\);
-
情况一：\(cnt+=2\) , \(sum *= (sz-1)*sz/2\)
-
情况二：\(cnt+=1\) , \(sum*=(sz-1)\)
-
情况三：无
code
#include<bits/stdc++.h>
using namespace std;
const int N= 1005 ;
int n,m; int head[N],tot;
struct E
{
int nxt,to;
} e[N];
void add(int u,int v)
{
e[++tot]={head[u],v};
head[u]=tot;
}
int dfn[N],low[N],t,num,sz[N];
stack <int> st;
bool cut[N];
vector<int> ds[N];
void tj(int s,int fa)
{
dfn[s]=low[s]=++num;
st.push(s);
if(head[s]==0&&s==fa)
{
ds[++t].push_back(s);
return;
}
int son=0;
for(int i=head[s];i;i=e[i].nxt)
{
int to=e[i].to;
if(!dfn[to])
{
son++;
tj(to,fa);
low[s]=min(low[s],low[to]);
if(low[to]>=dfn[s])
{
if(s!=fa||son>1) cut[s]=1;
t++;
int now;
while(now!=to)
{
now=st.top(); st.pop();
ds[t].push_back(now);
}
ds[t].push_back(s);
}
}
else low[s]=min(low[s],dfn[to]);
}
}
int main()
{
int T=0;
while(scanf("%d",&m)&&m!=0)
{
memset(head,0,sizeof(head));tot=0;
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(cut,0,sizeof(cut));
for(int i=1;i<N;i++) ds[i].clear();
n=0; t=0; num=0;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
n=max({x,y,n});
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tj(i,i);
long long ans=0,sum=1;
for(int i=1;i<=t;i++)
{
int cnt=0,sz=ds[i].size();
for(int j=0;j<sz;j++) if(cut[ds[i][j]]) cnt++;
if(cnt==0) ans+=2,sum*=((long long)sz*(sz-1)/2);
else if(cnt==1) ans++,sum*=(sz-1);
}
printf("Case %d: %lld %lld\n",++T,ans,sum);
}
return 0;
}
法二（dfs）
仍然是求连通块，并记录割点数量，可以考虑求出割点后用 \(dfs\) 统计。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
#define int long long
int m,n;
int head[N],tot;
struct E
{
int nxt,to;
} e[N];
void add(int u,int v)
{
e[++tot]={head[u],v};
head[u]=tot;
}
int dfn[N],low[N],num;
bool cut[N];
void tj(int u,int root)
{
dfn[u]=low[u]=++num;
int son=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v])
{
son++;
tj(v,root);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
if(u!=root||son>1) cut[u]=1;
}
else low[u]=min(low[u],dfn[v]);
}
}
int cnt[N],color,c[N];
bool vs[N];
map<int,map<int,int> > ge;
void dfs(int u,int fa)
{
cnt[color]++;
vs[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vs[v]||fa==v) continue;
if(cut[v])
{
if(!ge[color][v])
{
c[color]++;
ge[color][v]=1;
}
continue;
}
dfs(v,u);
}
}
void init()
{
n=0,num=0;
memset(head,0,sizeof(head)),tot=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
ge.clear();
memset(vs,0,sizeof(vs));
memset(cnt,0,sizeof(cnt));
memset(c,0,sizeof(c));
memset(cut,0,sizeof(cut));
color=0;
}
main()
{
int T=0;
while(scanf("%lld",&m)&&m!=0)
{
init();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%lld%lld",&x,&y);
add(x,y); add(y,x);
n=max({x,y,n});
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tj(i,i);
int ans=0,sum=1;
for(int i=1;i<=n;i++)
if(!cut[i]&&!vs[i])
{
color++,dfs(i,0);
if(c[color]==1) ans++,sum*=cnt[color];
else if(c[color]==0) ans+=2,sum*=((int)cnt[color]*(cnt[color]-1)/2);
}
printf("Case %lld: %lld %lld\n",++T,ans,sum);
}
return 0;
}
参考
https://www.cnblogs.com/Charlieljk/p/17888945.html
https://www.cnblogs.com/K8He/p/15889547.html
标签：head,矿场,int,memset,tanjar,dfn,low,sizeof,搭建 From： https://www.cnblogs.com/ppllxx/p/18084571