[图论][双联通分量][无向图仙人掌] UVALive 3514 Cactus

题意：求出给定图的生成子图里有多少个是仙人掌。

首先明确生成子图的概念：包括所有的顶点的子图（之前没有弄明白这个一直没有想出来），那么这个操作其实就很简单了，首先判断图形是否为仙人掌，如果是的话把其中所有的圈（其实在这里就是点双联通分量）所包含的边的数量算出来，Π(cnt[i]+1)即为结果（每个圈最多只能去掉一个边）。

首先，判断是否为仙人掌，这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来：对于任意一个dfs树上的节点u，他的反向边数量+他的子节点中low值小于pre[u]的数量<2，如果大于等于2说明这个节点附近已经产生了两个环了，不可能是仙人掌，反之如果所有点都满足这个要求，那么一定是仙人掌。

其次，求每一个圈的边数。这里如果是仙人掌的话，一定每个点双联通分量都是一个圈（否则就会被判定为非仙人掌，所以这里首先保证第一步的正确性是很重要的），这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了（注意是边的数量而不是点的）。

最后套一个无聊的高精度板子就ok了，因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高，1000位都满足不了开了100000位才过，至于吗呵呵

 

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int maxn=2e4+5;

struct BigInt
{
    const static int mod = 10000;
    const static int DLEN = 4;
    int a[10000],len;
    BigInt()
    {
        memset(a,0,sizeof(a));
        len = 1;
    }
    BigInt(int v)
    {
        memset(a,0,sizeof(a));
        len = 0;
        do
        {
            a[len++] = v%mod;
            v /= mod;
        }
        while(v);
    }
    BigInt(const char s[])
    {
        memset(a,0,sizeof(a));
        int L = strlen(s);
        len = L/DLEN;
        if(L%DLEN)
            len++;
        int index = 0;
        for(int i = L-1; i >= 0; i -= DLEN)
        {
            int t = 0;
            int k = i - DLEN + 1;
            if(k < 0)
                k = 0;
            for(int j = k; j <= i; j++)
                t = t*10 + s[j] - '0';
            a[index++] = t;
        }
    }
    BigInt operator +(const BigInt &b)const
    {
        BigInt res;
        res.len = max(len,b.len);
        for(int i = 0; i <= res.len; i++)
            res.a[i] = 0;
        for(int i = 0; i < res.len; i++)
        {
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/mod;
            res.a[i] %= mod;
        }
        if(res.a[res.len] > 0)
            res.len++;
        return res;
    }
    BigInt operator *(const BigInt &b)const
    {
        BigInt res;
        for(int i = 0; i < len; i++)
        {
            int up = 0;
            for(int j = 0; j < b.len; j++)
            {
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%mod;
                up = temp/mod;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len;
        while(res.a[res.len - 1] == 0 &&res.len > 1)
            res.len--;
        return res;
    }
    void output()
    {
        printf("%d",a[len-1]);
        for(int i = len-2; i >=0 ; i--)
            printf("%04d",a[i]);
        printf("\n");
    }
};


struct Edge
{
    int u,v;
    Edge ()
    {
        u=v=0;
    }
    Edge(int u,int v):u(u),v(v) {}
};
vector G[maxn];
int bcc[maxn];
stack S;


int pre[maxn],iscut[maxn],bccno[maxn],clk,bcc_cnt;
int gf;
int dfs(int u,int fa)
{
    int t1=0,t2=0;
    if(gf)
        return 0;
    int lowu=pre[u]=++clk;
    int child=0;
    int len=G[u].size();
    for(int i=0; ilowv)
            {
                t1++;
            }
            lowu=min(lowu,lowv);
            if(lowv>=pre[u])
            {
                iscut[u]=1;
                bcc_cnt++;
                while(1)
                {
                    Edge x=S.top();
                    S.pop();
                    bcc[bcc_cnt]++;
                    if(bccno[x.u]!=bcc_cnt)
                        bccno[x.u]=bcc_cnt;
                    if(bccno[x.v]!=bcc_cnt)
                        bccno[x.v]=bcc_cnt;
                    if(x.u==u&&x.v==v)
                        break;
                }
            }

        }
        else if(pre[v]=2)
        {
            gf=1;
            return 0;
        }
    }
    if(fa<0&&child==1)
        iscut[u]=0;
    return lowu;
}

void find_bcc(int n)
{
    while(!S.empty())S.pop();
    gf=0;//error1
    memset(pre,0,sizeof(pre));
    memset(bcc,0,sizeof(bcc));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    clk=bcc_cnt=0;
    dfs(1,-1);
}

void solve(int n)
{
    find_bcc(n);
    if(gf)
    {
        printf("0\n");
        return ;
    }
    for(int i=1;i<=n;i++)//error2
        if(!pre[i])
    {
        printf("0\n");
        return ;
    }
    BigInt ans(1);
    for(int i=1; i<=bcc_cnt; i++)
    {
        if(bcc[i]>1)
        {
            BigInt tmp(bcc[i]+1);
            ans=ans*tmp;
        }

    }
    ans.output();
}

int main()
{
    int n,m,k,u,v,fuck=0;
    while(~scanf("%d%d",&n,&m))
    {
        if(fuck)puts("");//final error....
        fuck=1;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&k,&u);
            for(int j=2; j<=k; j++)
            {
                scanf("%d",&v);
                G[u].push_back(v);
                G[v].push_back(u);
                u=v;
            }
        }
        solve(n);
        for(int i=1;i<=n;i++)G[i].clear();
    }
    return 0;
}