QOJ.ac

QOJ

時間限制: 1.0 s 記憶體限制: 256 MB 總分: 100 可 Hack ✓

#9246. 支配点

统计

给定一个包含 $n$ 个顶点的完全有向图 $G$。如果对于每个 $v \neq u$,要么存在边 $(u \to v)$,要么存在一个顶点 $w$ 满足 $(u \to w)$ 且 $(w \to v)$,则称顶点 $u$ 为支配点。

你需要找到该图中的 3 个不同的支配点。如果支配点的数量少于 3 个,输出 NOT FOUND

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5000$)。

接下来的 $n$ 行每行包含一个二进制字符串 $s_i$。如果 $s_u$ 的第 $v$ 个字符为 1,则存在边 $(u \to v)$;否则不存在该边。保证对于每个 $1 \le i < j \le n$,$s_{i,j} = 1$ 和 $s_{j,i} = 1$ 中恰有一个成立,且对于每个 $1 \le i \le n$,$s_{i,i} = 0$。

输出格式

输出一行,包含三个整数 $a, b, c$,表示你找到的答案;如果支配点不足 3 个,则输出 NOT FOUND

样例

样例输入 1

6
011010
000101
010111
100001
010100
100010

样例输出 1

3 1 4

样例输入 2

3
011
001
000

样例输出 2

NOT FOUND

样例输入 3

3
010
001
100

样例输出 3

1 3 2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.