2555: 单圈
内存限制:64 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:17
解决:0
题目描述
最近小f在研究图论的问题,小f对有向图的环特别感兴趣,但是小f希望找出图中所有的环,但是这个这个问题非常困难。
现在小f把这个问题化简,她只需要找到有向图中的一个单圈就可以了。
单圈的定义:单圈有三个点A,B,C组成,满足A-->B(有向边),B-->C,C-->A(存在A到B,B到C,C到A这三条有向边,且A,B,C为三个不同的点)
因为图中可能有多个单圈你只要输出其中字典序最小的那个即可,若找不到一个单圈,则输出-1。
输入
第一行一个正整数N,即该有向图有N个点,接下来一个N*N的邻接矩阵map,若map[i][j]=1,则表示点i到点j有一条有向边。
输出
一行用空格隔开的三个正整数或者找不到输出-1。
样例输入 复制
5
00100
10000
01001
11101
11000
样例输出 复制
1 3 2
提示
•40%的数据 N<=100
•100%的数据 N<=5000