[题解]（tarjan割点/点双）luogu_P3225

首先和割点有关，求割点，然后这些割点应该把这个图分成了多个点双，可以考虑点双的缩点，假如缩点做的话我们要分析每个点双的性质和贡献

先拿出一个点双来，如果它没有连接着割点，那么至少要建两个，以防止其中一个塌陷，

如果它连接着一个割点，那么需要建一个，因为可以通过割点到其他点双，或者割点塌陷走这个点双中的出口

如果它连接着两个以上的割点，那么不需要建，因为可以随意到达其他点双。

事实上没必要缩点，只要dfs每个点双，类似于联通块（题解中直接说联通块容易有歧义）染色，记录点数和连接的割点数目

对于情况1，方案贡献C（点数，2）=（点数）*（点数-1）/2；

情况2贡献就是点数。每次ans2*=贡献

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,m,num,tot,deg,ans1,T,root;long long ans2;

struct node{

    int v,nxt;

}e[maxn<<];

int head[maxn],cnt;

void add(int u,int v){

    e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;

}

int dfn[maxn],low[maxn],vis[maxn];

bool cut[maxn];

inline void init(){

    memset(head,,sizeof(head));

    memset(dfn,,sizeof(dfn));

    memset(low,,sizeof(low));

    memset(cut,,sizeof(cut));

    memset(vis,,sizeof(vis));

    cnt=tot=n=ans1=T=;ans2=;

}

void tarjan(int x,int fa){

    dfn[x]=low[x]=++tot;

    for(int i=head[x];i;i=e[i].nxt){

        int y=e[i].v;

        if(!dfn[y]){

            tarjan(y,x);

            low[x]=min(low[x],low[y]);

            if(low[y]>=dfn[x]){

                if(x==root)deg++;

                else cut[x]=;

            }

        }

        else if(y!=fa)low[x]=min(low[x],dfn[y]);

    }

}

void dfs(int x){

    vis[x]=T;

    if(cut[x])return;

    cnt++;

    for(int i=head[x];i;i=e[i].nxt){

        int y=e[i].v;

        if(cut[y] && vis[y]!=T)num++,vis[y]=T;//统计割点数

        if(!vis[y])dfs(y);

    }

}

int main(){int t=;

    while(){

        scanf("%d",&m);if(m==)break;

        init();

        for(int i=,u,v;i<=m;i++){

            scanf("%d%d",&u,&v);

            add(u,v);add(v,u);n=max(n,max(v,u));

        }

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

            if(!dfn[i])tarjan(root=i,);

            if(deg>=)cut[root]=;

            deg=;

        }

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

        if(!vis[i] && !cut[i]){

            T++;cnt=num=;

            dfs(i);

            if(!num)ans1+=,ans2*=cnt*(cnt-)/;

            if(num==)ans1++,ans2*=cnt;

        }

        printf("Case %d: %d %lld\n",++t,ans1,ans2);

    }

}

巴特西

[题解]（tarjan割点/点双）luogu_P3225_矿场搭建

最新文章

热门文章