自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:07:58，当前版本为作者最后更新于2025-01-05 13:04:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

知识

• tarjan。
• 乘法原理

解法

很明显这是一道有关连通分量的题目。可以发现，在同一个边双连通分量中最多有一个点属于集合 A，否则肯定不是最优的方案。

由于这是一个无向图，所以可以先 tarjan 求出强连通分量（由于无向，等价于边双）。然后缩点，可以发现这张图变成了一棵无根树。

接下来我们贪心。设强连通分量个数为 $k$，第 $i$ 个连通分量中节点个数为 $cnt_i$。

• $k=1$ 时：此时特判，有一个节点属于 A。有 $n$ 种情况。
• $k>1$ 时：此时对于每个叶子分量（度为 1），缩成它的节点中必须要有且仅有一个节点属于 A。非叶子分量不需要有节点属于 A，原因是它可以通向至少两个路径无重复的叶子分量。所以只需要统计叶子分量个数，并且同时将叶子分量中的节点个数乘起来，得到方案数即可。

代码

赛时代码，微丑。

// Author: chenly8128
// Created: 2025-01-05 10:52:42

#include <bits/stdc++.h>
using namespace std;
inline int read(void) {
	int res = 0;bool flag = true;char c = getchar();
	while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
	while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
	return flag ? res : -res;
}
const int MAXN = 2e5+10;
int n,m,u,v,now;
int col[MAXN],dfn[MAXN],low[MAXN],cnt[MAXN],dsfa,ans;
long long ans2 = 1;
vector <int> g[MAXN];
set <int> g2[MAXN];
stack <int> s;
void tarjan(int u,int fa) {
	dfn[u] = low[u] = ++dsfa;
	s.push(u);
	for (int v : g[u]) {
		if (v == fa) continue;
		if (!dfn[v]) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
		}
		else low[u] = min(low[u],dfn[v]);
	}
	if (dfn[u] == low[u]) {
		col[u] = ++now;
		cnt[now] = 1;
		while (s.top() != u) {
			col[s.top()] = now;
			s.pop();
			cnt[now]++;
		}
		s.pop();
	}
}
int main (void) {
	n = read();m = read();
	for (int i = 1;i <= m;i++) {
		u = read();v = read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	tarjan (1,-1);
	for (int i = 1;i <= n;i++)
		for (int j : g[i])
			if (col[j] != col[i]) g2[col[i]].insert(col[j]);
	for (int i = 1;i <= now;i++)
		if (g2[i].size() == 1) {
			ans++;
			ans2 = ans2 * cnt[i] % 1000000007;
		}
	if (ans == 0) cout << 1 << ' ' << n << '\n';
	else cout << ans << ' ' << ans2 << '\n';
	return 0;
}