acwing396.矿场搭建(Tarjan点双连通分量)

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见&＃xff0c;希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口&＃xff0c;使得无论哪一个挖煤点坍塌之后&＃xff0c;其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序&＃xff0c;用来计算至少需要设置几个救援出口&＃xff0c;以及不同最少救援出口的设置方案总数。

输入格式
输入文件有若干组数据&＃xff0c;每组数据的第一行是一个正整数 N&＃xff0c;表示工地的隧道数。

接下来的 N 行每行是用空格隔开的两个整数 S 和 T&＃xff0c;表示挖煤点 S 与挖煤点 T 由隧道直接连接。

注意&＃xff0c;每组数据的挖煤点的编号为 1∼Max&＃xff0c;其中 Max 表示由隧道连接的挖煤点中&＃xff0c;编号最大的挖煤点的编号&＃xff0c;可能存在没有被隧道连接的挖煤点。

输入数据以 0 结尾。

输出格式
每组数据输出结果占一行。

其中第 i 行以 Case i: 开始&＃xff08;注意大小写&＃xff0c;Case 与 i 之间有空格&＃xff0c;i 与 : 之间无空格&＃xff0c;: 之后有空格&＃xff09;。

其后是用空格隔开的两个正整数&＃xff0c;第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口&＃xff0c;第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 264&＃xff0c;输出格式参照以下输入输出样例。

数据范围
1≤N≤500&＃xff0c;
1≤Max≤1000

输入样例&＃xff1a;
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
输出样例&＃xff1a;
Case 1: 2 4
Case 2: 4 1


#include
using namespace std;
const int N &＃61; 1e3 &＃43; 10;
const int M &＃61; 1e3 &＃43; 10;
typedef unsigned long long ULL;
struct Edge{int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){edge[cnt].v &＃61; v;edge[cnt].next &＃61; head[u];head[u] &＃61; cnt &＃43;&＃43;;
}
int in[N];
int sccno;
vector<int>g[N];
int low[N],num[N],dfn;
int sta[N],top;
int is_solate[N],cut[N];
//点双连通分量
void Tarjan(int u,int fa){num[u] &＃61; low[u] &＃61; &＃43;&＃43;dfn;if(fa &＃61;&＃61; -1 && head[u] &＃61;&＃61; -1){ //孤立节点特判sccno &＃43;&＃43;;g[sccno].push_back(u);is_solate[sccno] &＃61; true;return;}sta[top &＃43;&＃43;] &＃61; u;int child &＃61; 0;for(int i &＃61; head[u];~i;i &＃61; edge[i].next){int v &＃61; edge[i].v;if(v &＃61;&＃61; fa)continue;if(!num[v]){child &＃43;&＃43;;Tarjan(v,u);low[u] &＃61; min(low[u],low[v]);if(low[v] >&＃61; num[u]){if(fa !&＃61; -1)cut[u] &＃61; true;int t;sccno &＃43;&＃43;;while(true){t &＃61; sta[-- top];g[sccno].push_back(t);if(t &＃61;&＃61; v)break;}g[sccno].push_back(u);}}else low[u] &＃61; min(low[u],num[v]);}if(fa &＃61;&＃61; -1 && child >&＃61; 2)cut[u] &＃61; true;
}
int main(){int m &＃61; 0;int x,y;int n;int T &＃61; 0;while(cin>>m,m){n &＃61; 0;memset(head,-1,sizeof head);memset(num,0,sizeof num);memset(low,0,sizeof low);memset(cut,0,sizeof cut);dfn &＃61; 0,cnt &＃61; 0;for(int i &＃61; 1;i <&＃61; sccno;i &＃43;&＃43;)g[i].clear();sccno &＃61; 0;for(int i &＃61; 0;i < m;i &＃43;&＃43;){cin>>x>>y;add(x,y),add(y,x);n &＃61; max(n,max(x,y));}for(int i &＃61; 1;i <&＃61; n;i &＃43;&＃43;){if(!num[i])Tarjan(i,-1);}ULL res &＃61; 0;ULL c &＃61; 1;for(int i &＃61; 1;i <&＃61; sccno;i &＃43;&＃43;){int d &＃61; 0;for(auto &a : g[i]){if(cut[a])d &＃43;&＃43;;}int a &＃61; g[i].size() - d;if(d &＃61;&＃61; 0){if(a &＃61;&＃61; 1)res &＃43;&＃61; 1;else res &＃43;&＃61; 2,c *&＃61; (a * (a - 1) / 2);}else if(d &＃61;&＃61; 1){if(a &＃61;&＃61; 1)res &＃43;&＃61; 1;else res &＃43;&＃61; 1,c *&＃61; a;}}printf("Case %lld: %lld %lld\n",&＃43;&＃43;T,res,c);}return 0;
}