102136: [AtCoder]ABC213 G - Connectivity 2
Description
Score : $600$ points
Problem Statement
Given is a simple undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1,2,\dots,N$, the edges are numbered $1,2,\dots,M$, and Edge $i$ connects Vertex $a_i$ and Vertex $b_i$.
Consider removing zero or more edges from $G$ to get a new graph $H$. There are $2^M$ graphs that we can get as $H$. Among them, find the number of such graphs that Vertex $1$ and Vertex $k$ are directly or indirectly connected, for each integer $k$ such that $2 \leq k \leq N$.
Since the counts may be enormous, print them modulo $998244353$.
Constraints
- $2 \leq N \leq 17$
- $0 \leq M \leq \frac{N(N-1)}{2}$
- $1 \leq a_i \lt b_i \leq N$
- $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$
Output
Print $N-1$ lines. The $i$-th line should contain the answer for $k = i + 1$.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
2 1
We can get the following graphs as $H$.
- The graph with no edges. Vertex $1$ is disconnected from any other vertex.
- The graph with only the edge connecting Vertex $1$ and $2$. Vertex $2$ is reachable from Vertex $1$.
- The graph with only the edge connecting Vertex $2$ and $3$. Vertex $1$ is disconnected from any other vertex.
- The graph with both edges. Vertex $2$ and $3$ are reachable from Vertex $1$.
Sample Input 2
5 6 1 2 1 4 1 5 2 3 2 5 3 4
Sample Output 2
43 31 37 41
Sample Input 3
2 0
Sample Output 3
0
Input
题意翻译
#### 题目大意 给一张 $N$ 个点 $M$ 条边的简单无向图 $G$。考虑删去 $0$ 条以上的边构成一张新图。对于每个点 $k(2\leq k\leq N)$,求有多少张新图满足点 $k$ 与点 $1$ 连通(模 $998244353$)。 #### 输入格式 第 $1$ 行两个整数 $N$,$M$,表示点数和边数。 第 $2$ ~ $M+1$ 行每行两个整数 $a$, $b$ 表示 $a$ 与 $b$ 间有一条无向边。 #### 输出格式 共 $N-1$ 行。第 $i$ 行输出一个整数表示满足点 $1$ 与点 $(i+1)$ 连通的新图数。Output
问题描述
给定一个具有$N$个顶点和$M$条边的简单无向图$G$。顶点编号为$1,2,\dots,N$,边编号为$1,2,\dots,M$,边$i$连接顶点$a_i$和顶点$b_i$。
考虑从$G$中删除零条或多条边,得到一个新的图$H$。我们可以通过$H$得到$2^M$个图。其中,对于每个满足$2 \leq k \leq N$的整数$k$,找出顶点$1$和顶点$k$直接或间接连接的图的数量。
由于计数可能非常庞大,请将它们对$998244353$取模。
约束
- $2 \leq N \leq 17$
- $0 \leq M \leq \frac{N(N-1)}{2}$
- $1 \leq a_i \lt b_i \leq N$
- 如果$i \neq j$,则$(a_i, b_i) \neq (a_j, b_j)$。
- 输入中的所有值都是整数。
输入
输入将从标准输入按以下格式给出:
$N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$
输出
打印$N-1$行。第$i$行应包含对于$k = i + 1$的答案。
样例输入 1
3 2 1 2 2 3
样例输出 1
2 1
我们可以得到以下作为$H$的图。
- 没有边的图。顶点$1$与任何其他顶点断开连接。
- 仅包含连接顶点$1$和$2$的边的图。顶点$2$可以从顶点$1$到达。
- 仅包含连接顶点$2$和$3$的边的图。顶点$1$与任何其他顶点断开连接。
- 包含两条边的图。顶点$2$和$3$可以从顶点$1$到达。
样例输入 2
5 6 1 2 1 4 1 5 2 3 2 5 3 4
样例输出 2
43 31 37 41
样例输入 3
2 0
样例输出 3
0