众所周知，Bfk家的后院有一片胡萝卜田
这片田地很受兔子们的喜爱，兔子们为了方便偷吃胡萝卜，在地下打出了一片洞穴网络。Bfk早就发现了它家的萝卜田里兔子泛滥的情形，因此，它决定先外出旅游几天，让兔子们放松警惕，回家时再将兔子们一网打尽。
具体的，我们可以将洞穴网络抽象成一个n条边的图。bfk的策略是，随机堵住某个节点，如果这个点是地下网络的必经之路，那么它就可以守洞待兔了。兔子们并不想坐以待毙，因此它们决定在某些节点挖出通向地面的出口，使得无论bfk堵住哪个节点，兔子们都可以直接从某个出口溜走。
但是兔子们只会计算1+1=2，对于如此复杂的问题，它们毫无头绪。请你帮忙计算一下，兔子们至少需要挖多少个出口才能满足上述条件，以及在出口数最少的情况下，出口的分布方式有多少种
第一行一个正整数n，表示地下网络的边数
接下来n行，每行两个整数u,v表示有一条双向边连通了u,v两点
输出一行两个整数 cnt,tot。其中，cnt 表示最少出口数，tot表示在出口数最少的情况下，设置出口的方案数在模998244353意义下的值
对于 20% 的数据，n≤15
对于 40% 的数据，n≤10000
对于 68% 的数据，n≤100000
对于全部数据，n≤2000000 ，数据有梯度
保证有 16% 的数据满足，该图任意两点间至少有两条点不重复的路径
保证无自环，但不保证无重边
看到题很容易想到割点，割点把图分成很多点连通分量。
如果没有割点，那么需要选两个点，只选一个点的话，如果那个点被蹲就没地方出去了。方案数c(2,num)
对于上或下两个连通分量，他们都有一个割点，只需要选一个出口，如果蹲割点，就可以在各自出口出；蹲自己的出口，就可以去对面的出口。
对于(2,5,6)中间这个连通分量，有两个割点，不需要选出口，因为可以到旁边的连通分量去。
所以先tarjan求出割点，再遍历每个连通分量，根据割点个数分类即可。
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=2000005; const int mod=998244353; int n,m,cur; ll timer,num,cnt; ll ans1,ans2=1; int dfn[maxn],low[maxn]; int vis[maxn]; bool cut[maxn]; vector<int>e[maxn]; template<class T>inline void read(T &x){ x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int max(int x,int y){return x>y ? x : y ;} int min(int x,int y){return x<y ? x : y ;} void tarjan(int u,int fa){ int son=0; low[u]=dfn[u]=++cur; for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[v],low[u]); if((++son>1&&!fa)||(dfn[u]<=low[v]&&fa)) cut[u]=true; } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } void dfs(int u){ vis[u]=timer; num++;//连通分量非割点 for(unsigned int i=0;i<e[u].size();i++){ int v=e[u][i]; if(cut[v]&&vis[v]!=timer){ cnt++;//割点 vis[v]=timer; } if(!vis[v]) dfs(v); } } int main(){ freopen("rabbit.in","r",stdin); freopen("rabbit.out","w",stdout); read(m); for(int i=1;i<=m;i++){ int x,y; read(x);read(y); e[x].push_back(y); e[y].push_back(x); n=max(n,max(x,y)); } for(int i=1;i<=n;i++) if(!dfn[i]){ cur=0; tarjan(i,0); } for(int i=1;i<=n;i++) if(!vis[i]&&!cut[i]){ ++timer; cnt=num=0; dfs(i); if(!cnt){ if(num==1)//孤点 ans1++; else{ ans1+=2; ans2=ans2*num*(num-1)/2%mod; } } else if(cnt==1){ ans1++; ans2=ans2*num%mod; } } printf("%lld %lld",ans1,ans2); }
原文：https://www.cnblogs.com/sto324/p/11182233.html