寒假训练——搜索 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). A_i,?j?=?1 if the graph has an edge going from vertex i to vertex j, otherwise A_i,?j?=?0. A_i,?j stands for the j-th character in the i-th line.

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

Output

Print three distinct vertexes of the graph a₁, a₂, a₃ (1?≤?a_i?≤?n), such that A_a1,?a2?=?A_a2,?a3?=?A_a3,?a1?=?1, or "-1", if a cycle whose length equals three does not exist.

If there are several solutions, print any of them.

Examples

5
00100
10000
01001
11101
11000

1 3 2 

5
01111
00000
01000
01100
01110

-1

#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;
}

寒假训练——搜索 K - Cycle

原文：https://www.cnblogs.com/EchoZQN/p/10351489.html