P3225 [HNOI2012] 矿场搭建求调

#include <bits/stdc++.h>

#define int long long

using namespace std;
using i64 = long long;

const int N = 50010;

vector<int> e1[N], e2[N];
int n = 10000, m;

int dfn[N], low[N], cnt, tot;
int stk[N], top;
vector<int> allver;
int root;

void tarjan(int u, int fa) {
	allver.push_back(u);
	dfn[u] = low[u] = ++cnt;
	stk[++top] = u;
	for (int i = 0; i < e1[u].size(); i++) {
		int to = e1[u][i];
		if (!dfn[to]) {
			tarjan(to, u);
			low[u] = min(low[u], low[to]);
			if (low[to] >= dfn[u]) {
				tot++;
				int p = 0;
				do {
					p = stk[top];
					top--;
					e2[p].push_back(tot);
					e2[tot].push_back(p);
				} while (p != to);
				e2[u].push_back(tot);
				e2[tot].push_back(u);
			}
		}
		else if (to != fa) low[u] = min(low[u], dfn[to]);
	}
}

set<int> p;
i64 ans1, ans2;
bool g[N];

void process() {
	p.clear();
	for (int j = 0; j < allver.size(); j++) {
		int i = allver[j];
		if (e2[i].size() == 1) {
			p.insert(e2[i][0]);
		}
	}
	if (p.size() == 1) {
		ans1 += 2, ans2 *= 1ll * allver.size() * (allver.size() - 1) / 2;
		return;
	}
	ans1 += p.size();
	for (auto x : p) ans2 *= (e2[x].size() - 1);
}

void solve() {
	memset(g, 0, sizeof(g));
	for (int i = 0; i < N; i++) e1[i].clear();
	for (int i = 0; i < N; i++) e2[i].clear();
	ans1 = 0, ans2 = 1;
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	cnt = 0;
	tot = n;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u] = g[v] = 1;
		if (u == v) continue;
		e1[u].push_back(v);
		e1[v].push_back(u);
	}
	
	for (int i = 1; i < N; i++) {
		sort(e1[i].begin(), e1[i].end());
		e1[i].erase(unique(e1[i].begin(), e1[i].end()), e1[i].end());
	}
	for (int i = 1; i < N; i++) {
		if (!g[i]) continue;
		if (!dfn[i]) {
			root = i;
			top = 0;
			allver.clear();
			tarjan(i, i);
			process();
		}
	}
	cout << ans1 << ' ' << ans2 << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for (int T = 1; ; T++) {
		cin >> m;
		if (!m) break;
		cout << "Case " << T << ": ";
		solve();
	}
	return 0;
}