HBCPC 2020 刪點

題目

作者 ICPC Team

單位 北京郵電大學

小河得到了一個包含n個點的無向圖。他要選取一個點的集合（可以為空），將其中的點依次刪掉。對于選出的這個集合，他還需要選取一個合適的刪點順序，使得刪的過程中，任何點在被刪掉的時刻依然與至少一個未被刪掉的點相連（請參考樣例）。

刪著刪著，他發現，不是所有的集合都能找到一個滿足條件的刪點順序。比如，對于下圖：

對于集合{4},{1,4},{2,4},{3,4}都不能找出滿足條件的方案，因為無論如何，在刪除4的時候，它都不與任何點相連——事實上，4在任何時刻都不與其它點相連。

他希望知道，有多少個不同的集合可以找到一種滿足條件的刪點順序。由于方案數可能很大，請輸出答案對998244353取模后的結果。

題目保證不會出現自環。

輸入格式

第一行兩個數字n,m(1≤n,m≤106)，表示有n個點和m條邊。

接下來m行，每行兩個數字x,y(1≤x,y≤n,x=y)，表示x和y之間有一條邊相連。

輸出格式

輸出存在符合條件刪點順序的集合個數

樣例輸入

5 4
1 2
2 3
2 4
3 5

樣例輸出

31

樣例解釋

下面是滿足條件的31種方案：

?{1},{2},{3},{4},{5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5},{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5},{1,2,3,4}{1,2,3,5}{1,2,4,5}{1,3,4,5}{2,3,4,5}

以{1,2,5}為例，按照1?2?5的順序刪除即可滿足要求，如下圖所示：

唯一一個找不到滿足條件刪除順序的集合是{1,2,3,4,5}，因為不管怎么刪，最后一個點在刪除的時候一定不與任何點相鄰

代碼長度限制

16 KB

Java (javac)

時間限制

6000 ms

內存限制

512 MB

其他編譯器

時間限制

3000 ms

內存限制

512 MB

思路

? 對于圖\(G<V, E>\), 考慮每個單獨的連通塊而言， 我們設刪除集合為\(S\), 只要\(S \subset V\), 即\(S\)不包含所有點，這樣的序列就是和法的，那么對于一個單獨的連通塊而言其方案數\(cnt_i = 2^{v_i} - 1\), 其中\(v_i\)為當前連通塊內的點數, 那么所有方案數\(CNT = \prod_{i = 1}^{num}(2^{v_i} - 1)\)。

? 證明對于單獨的連通塊方案數為\(2^{v_i} - 1\) ：構造一種方案，我們考慮當前圖的生成樹， 構造出一種合法刪點順序對于任何非全集，刪點集合始終保持兩種狀態，有葉子節點和無葉子節點，對于葉子節點顯然我們都可以直接刪除， 對于非葉子節點，我們可以忽略圖中該點，再去刪掉別的葉子節點，另外該點若是集合中最后一個點則可以直接刪除。由于全集中，我們刪去\(n - 1\)個點后，最后一個點不滿足條件，所以全集不是合法方案。

Code

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e6 + 10, M = 2e6 + 10, mod = 998244353;

int n, m;

int h[N], e[M], ne[M], idx;

bool st[N];

int cnt;

void add(int a, int b) {
	ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}

i64 qmi(i64 a, i64 b) {
	i64 res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

void dfs(int u) {
	if (st[u]) return;

	st[u] = true;

	cnt ++;

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (st[v]) continue;

		dfs(v);
	}
}

int main() {
	memset(h, -1, sizeof h);
	
	std::cin >> n >> m;

	for (int i = 1; i <= m; i ++) {
		int x, y; 
		std::cin >> x >> y;
		add(x, y), add(y, x);
	}

	i64 ans = 1;

	for (int i = 1; i <= n; i ++) {
		if (!st[i]) {
			cnt = 0;
			dfs(i);
			ans = ans * (qmi(2, cnt) - 1) % mod;
		}	
	}

	std::cout << ans;
}