TJ monthly 图灵姬月赛 2020.1

1002. Zeratul与强连通图

时间限制: C/C++/Pascal 1000 ms; Others 2000 ms

内存限制: 256 MB

题目描述:

由于异虫的侵袭,Shakuras正在施行交通管制。Shakuras有 n 条横向(东西向)街道和 m 条纵向(南北向)街道,现在它们都要变成单行道。

n 条横向街道和 m 条纵向街道形成了 n*m 个路口。

现在Zeratul想要知道,是否存在两个路口a,b,使得a无法到达b。

输入格式:

第一行包括整数 T ,代表数据组数。

对于每组数据,第一行包括两个整数 n m ,代表横向街道和纵向街道的数量。

第二行包括一个长度为 n 的字符串,由>和<组成,代表从北到南的 n 个横向街道的方向。>代表街道是向东的单行道,<代表街道是向西的单行道。

第三行包括一个长度为 m 的字符串,由v和^组成,代表从西到东的 m 个纵向街道的方向。v代表街道是向南的单行道,^代表街道是向北的单行道。

输出格式:

对于每组样例,输出一行YES或者NO,代表是否存在两个路口a,b,使得a无法到达b。

样例:

Input
Copy
1
3 3
><>
v^v
Output
Copy
YES

数据范围及提示

对于20%的数据, n=m=2

对于40%的数据, n=2 m=2

对于60%的数据, n,m \le 10

对于80%的数据, n,m \le 200

对于100%的数据, T \le 20 2 \le n,m \le 2000

已结束

积分

题目 计分
1001 100
1002 100
1003 100
1004 100
这里显示的是你在现在一次提交正确所获得的计分。
题目信息

题目类型:传统题

文件IO

输入文件名:tarjan.in

输出文件名:tarjan.out

AMAZE UI
Hello world!