48 lines
1.9 KiB
Markdown
48 lines
1.9 KiB
Markdown
|
# 信息传递
|
|||
|
|
by Chen Ning
|
|||
|
|
|
|||
|
|
时间限制: 1000 ms 内存限制: 6000 KB
|
|||
|
|
## 问题描述
|
|||
|
|
某组织在执行任务时需要进行信息传递，为保证信息传递的安全性，每个节点只能向特定的某些节点发送消息，已知有N个节点，初始信息由0号节点开始发送，现在系统的设计师需要确认所设计的连接方式能否使得所有节点最终都收到0号节点发送的消息。为了保证系统的鲁棒性，系统设计师还需要考虑若有信道损坏是否会影响信息的传递。具体来说，给定M条可能毁坏的信道，需要依次考虑只有一条信道被毁坏时是否所有节点仍能收到0号节点发送的信息。下面是一幅与输入输出样例对应的示意图，绿色节点能收到0号节点发送的信息，橙色节点则无法收到。
|
|||
|
|
## 输入格式
|
|||
|
|
输入共N+M+1行
|
|||
|
|
|
|||
|
|
第一行为两个正整数，第一个正整数N表示节点总数，第二个正整数M表示可能被破坏的信道数
|
|||
|
|
|
|||
|
|
接下来的N行依次给出从0号节点到N-1号节点能发送消息的节点；每行第一个数n表示该节点能传递消息的节点个数，后面n个数表示能传递消息的节点编号，同一行的数之间用空格分隔。
|
|||
|
|
|
|||
|
|
接下来的M行对应M个可能毁坏的信道，每行两个数i j，用空格分隔，表示从节点i到节点j的信道毁坏。
|
|||
|
|
## 输出格式
|
|||
|
|
输出为M+1行，每行一个正整数，第一行对应原始情况，后面M行依次对应M条信道毁坏后的情况。若对应情况下所有节点都能收到0号节点发送的消息，则输出1，反之输出0。
|
|||
|
|
## 输入样例
|
|||
|
|
> 4 2
|
|||
|
|
>
|
|||
|
|
> 2 1 2
|
|||
|
|
>
|
|||
|
|
> 2 2 3
|
|||
|
|
>
|
|||
|
|
> 0
|
|||
|
|
>
|
|||
|
|
> 1 0
|
|||
|
|
>
|
|||
|
|
> 0 1
|
|||
|
|
>
|
|||
|
|
> 0 2
|
|||
|
|
## 输出样例
|
|||
|
|
> 1
|
|||
|
|
>
|
|||
|
|
> 0
|
|||
|
|
>
|
|||
|
|
> 1
|
|||
|
|
## 提示
|
|||
|
|
1. 测试样例情况：
|
|||
|
|
|
|||
|
|
1-4测试样例：N<2^10，M=0
|
|||
|
|
|
|||
|
|
5-7测试样例：N<2^16，M=0
|
|||
|
|
|
|||
|
|
8-10测试样例：N<2^16，M<2^16
|
|||
|
|
|
|||
|
|
对于所有测试样例，边数E<2^20
|
|||
|
|
|
|||
|
|
2. 图中无自环、重边
|