题解：SP16185/UVA1108 BUSINESS - Mining your own business

将题目进行转化：在图中安装若干个太平井后，使得任意删除一个点，每个点双连通分量中都之后有一个太平井。

由题意可知，安装太平井，肯定与割点有关。因此，我们先求出无向图中的割点。

void dfs (int u,int fa)
{
    low[u] = dfn[u] = ++times;//时间戳 
    int child = 0;
    for (int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
        ++child;
            dfs (v,u);
            low[u] = min (low[u],low[v]);
            if (dfn[u] <= low[v])//为割点 
                iscut[u] = 1;
        }
        else if (v != fa && dfn[v] < dfn[u])//反向边 
            low[u] = min (low[u],dfn[v]);
    }
    if (fa < 0 && child == 1) iscut[u] = 0;//特殊情况 
}

把所有边双向存入后，调用 dfs (1,-1)，然后根据 iscut[i] 的布尔值判断该点是否为割点。

点双连通分量与割点数量的关系决定了安装太平井的数量，所以我们在求割点的同时也要记录每一个点双连通分量。

这里我们可以使用 set <int> 变量名，在记录每一个元素的同时也可以将相同的元素去除。在 dfs (u,fa) 函数的基础上修改一下即可，结合注释，代码应该很好理解。

void dfs (int u,int fa)
{
    low[u] = dfn[u] = ++times;//时间戳 
    int child = 0;
    for (int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if (!dfn[v])
        {
            ++child;
            st.push (i);//加入元素 
            dfs (v,u);
            low[u] = min (low[u],low[v]);
            if (dfn[u] <= low[v])//为割点 
            {
                iscut[u] = 1;
                ++bcc_cnt;//点双连通分量的数量 
                while (1)
                {    
                    int x = st.top ();st.pop ();
                    con[bcc_cnt].insert (dis[x]);//两条相邻的边加入其中 
                    con[bcc_cnt].insert (to[x]);
                    if (dis[x] == u && to[x] == v) break;//退出循环的条件        
                }
            }
        }
        else if (v != fa && dfn[v] < dfn[u])//反向边 
        {
            st.push (i);//加入元素 
            low[u] = min (low[u],dfn[v]);
        }
    }
    if (fa < 0 && child == 1) iscut[u] = 0;//特殊情况 
}

最后就是答案的求解了，对于一个点双连通分量有以下的情况：

全部连通，割点数为 $0$。此时若连接点坍塌，需要 $2$ 个太平井才能符合要求。设连通块大小为 $sz$，则任意选择两个点的方案数为 $C_{sz}^{2} = \frac{sz \times (sz - 1)}{2}$。
割点数为 $1$。此时若连接点坍塌，只需要 $1$ 个太平井才能符合要求。设连通块大小为 $sz$，则任意选择一个的方案数为 $sz - 1$。
割点数大于 $1$。此时易得若缺少一个割点，该点双连通分量仍然联通，因此不需要安装。

部分代码如下，注意需要使用乘法原理，且需要注意变量的类型。

ull ans1 = 0,ans2 = 1;//注意类型 
for (int i = 1;i <= bcc_cnt;++i)
{
    ull num = 0,sz = 0;
    for (set <int> :: iterator j = con[i].begin ();j != con[i].end ();++j)
    {
        ++sz;//该连通块的大小 
        if (iscut[*j]) ++num;//割点数量 
    }    
    if (num == 0) ans1 += 2,ans2 *= sz * (sz - 1) / 2;//为 0 的情况 
    else if (num == 1) ++ans1,ans2 *= (sz - 1);//为 1 的情况 
}

写在最后的话：

由于为多组数据，每次得出答案后记得初始化。
若有问题，及时提出，记得点个赞再走哦qwq！