这道题挺难的,可以加深对割点的理解,还有,排列组合好重要了,分连通块,然后乘法原理(加法原理计数什么的)
传送门 https://www.luogu.org/problem/P3225
省选oi题好难啊QAQ
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #define maxn 10000 using namespace std; vector<int>G[maxn]; void insert(int be, int en) { G[be].push_back(en); } int low[maxn], dfn[maxn], vis[maxn], df; int cnt[maxn]; void tarjan(int root ,int x) { low[x] = dfn[x] = ++df; int chal = 0; for (int i = 0; i < G[x].size(); i++) { int p = G[x][i]; if (!dfn[p]) { tarjan(root, p); chal++; low[x] = min(low[x], low[p]); if (root != x) { if (low[p] >= dfn[x]) { cnt[x] = 1; } } else { if (chal >= 2) { cnt[root] = 1; } } } else { low[x] = min(low[x], dfn[p]); } } } int num, cn; int gp; void dfs(int x) { if (cnt[x]) return; if (vis[x]) return; num++; vis[x] = gp; for (int i = 0; i < G[x].size(); i++) { int p = G[x][i]; if (cnt[p] && vis[p] != gp) { cn++; vis[p] = gp; } dfs(p); } } int main() { int m; int ccc = 0; while (~scanf("%d", &m) && m) { int n = -1; int be, en; ccc++; memset(dfn, 0, sizeof(dfn)); memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < m; i++) { scanf("%d %d", &be, &en); insert(be, en); insert(en, be); n = max(be, n); n = max(en, n); } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i, i); } long long ans1 = 0, ans2 = 1; for (int i = 1; i <= n; i++) { if (!vis[i] && !cnt[i]) { cn = num = 0; gp++; dfs(i); if (cn == 0) { ans1 += 2; ans2 *= num * (num - 1) / 2; } if (cn == 1) { ans1 += 1; ans2 *= num; } } } printf("Case %d: %lld %lld\n",ccc, ans1, ans2); for (int i = 0; i <= n; i++) G[i].clear(); } return 0; }