寒假训练——搜索 K - Cycle

A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes u and v (u ≠ v) exists either an edge going from u to v, or an edge from v to u.

You are given a tournament consisting of n vertexes. Your task is to find there a cycle of length three.

Input

The first line contains an integer n (1 ≤ n ≤ 5000). Next n lines contain the adjacency matrix A of the graph (without spaces). Ai, j = 1 if the graph has an edge going from vertex i to vertex j, otherwise Ai, j = 0. Ai, j stands for the j-th character in the i-th line.

It is guaranteed that the given graph is a tournament, that is, Ai, i = 0, Ai, j ≠ Aj, i (1 ≤ i, j ≤ n, i ≠ j).

Output

Print three distinct vertexes of the graph a1, a2, a3 (1 ≤ ai ≤ n), such that Aa1, a2 = Aa2, a3 = Aa3, a1 = 1, or "-1", if a cycle whose length equals three does not exist.

If there are several solutions, print any of them.

Examples

Input
5
00100
10000
01001
11101
11000
Output
1 3 2 
Input
5
01111
00000
01000
01100
01110
Output
-1


cycle
思路:
就是用搜索,以一排展开,dfs含有两个参数,这两个参数代表这个位置为1,所有,再去搜索,按照没有搜索的一排展开,
找到这个值。
AC之后,之前这个题目思路有一些混乱,再整理一下
在一个dfs要考虑到三个数,dfs里面的两个参数就是其中两个数,然后找到这两个参数中任意一个对应得第三个数,
再判断第三个数和另一个参数有没有相互对应,有就返回了,没有继续判断这一行有没有被标记,标记了就不用,没有标记就
继续进行搜索。值得确定得是,第一确实每一个都搜到了,没有遗漏,第二,就是搜索得递归,可以再仔细想想
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn=5050;
char ana[maxn][maxn];
bool bna[maxn][maxn],vis[maxn];
int n,a,b,c;

int dfs(int x,int y)
{
    vis[x]=1;
    for(int i=1;i<=n;i++)
    {
        if(bna[x][i])
        {
            if(y&&bna[i][y])
            {
                a=y;
                b=x;
                c=i;
                return 1;
            }
            if(!vis[i]) if(dfs(i,x)) return 1;
        }
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ana[i]+1);
        for(int j=1;j<=n;j++)
        {
            bna[i][j]=ana[i][j]-'0';
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            if(dfs(i,0))
            {
                printf("%d %d %d\n",a,b,c);
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}

  

上一篇:LeetCode OJ 24. Swap Nodes in Pairs


下一篇:1015 德才论 (25 分)2 3 4测试点不过