logo AlgoBeat OnlineJudge
登录 注册

#101846. [BZOJ 1846] [HDOJ]2471 History of Languages

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定两个确定性有限状态自动机(DFA),判断 是否等价(即对于任意输入串,输出都一致)。

输入格式

输入有若干组数据,对于每一组输入数据:

第一行一个正整数 表示字符集大小。

接下来描述 ,对于每一个 DFA:

第一行一个整数 表示状态数。

接下来 行,第 行有 个数 表示状态 是否为终态,若 表示状态 是终态,否则不是; 表示状态 通过字符 转移到状态 ,若 则表示无此转移边。

输出格式

对第 组数据,输出单独一行 Case #i: Yes 或者 Case #i: No 表示第 组数据中两个 DFA 是否等价。

样例

样例输入 #1

2
3
1 -1 1
0 -1 2
0 -1 0
2
1 -1 1
0 -1 0
3
4
1 -1 -1 1
1 -1 -1 2
1 -1 -1 3
1 -1 -1 1
2
1 -1 -1 1
1 -1 -1 0
0

样例输出 #1

Case #1: No
Case #2: Yes

数据范围与提示