Codeforces Beta Round #88 C. Cycle —

题目链接：http://codeforces.com/problemset/problem/117/C

C. Cycle

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

output

1 3 2

input

output

-1

题解：

由于只有三个点，所以在dfs时：对于当前点，判断下一个点是否能到达上一个点。（相当于枚举当前点）。

学习之处：

1.做题技巧：如果题目的限定很小，那么就可以直接枚举，不必要找到通用的方法，找到解决此题的方法即可。

例如：http://blog.csdn.net/dolfamingo/article/details/62887883

此题的限定条件是3条边，那么可以直接枚举第二条边。找到能解决三条边的方法即可，不必寻找能解决n条边的方法。但是题后要思考，寻找通用的方法。

2.有关找环的另一道题：http://blog.csdn.net/dolfamingo/article/details/72566330

3.思考题：找大小为m的环又该怎么办呢？

此题环的大小为3，所以刚好可以用vis[]来防止重复访问，但是当环为m时，就不能这样了（因为即便某些点被访问过，但是仍能与当前的路径构成m环），这个问题值得思考。

代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const double eps = 1e-6;

const int INF = 2e9;

const LL LNF = 9e18;

const int mod = 1e9+7;

const int maxn = 5e3+10;

int n;

int g[maxn][maxn], vis[maxn];

int dfs(int u, int pre)

{

    vis[u] = 1;

    for(int i = 1; i<=n; i++)

    {

        if(g[u][i])  //u能到v

        {

            if(pre!=-1 && g[i][pre])    //不管i有没被访问，只要能构成3环就可以了。

            {

                printf("%d %d %d", pre, u, i);

              return 1;

            }

            if(!vis[i] && dfs(i,u)) //如果i没有被访问，则访问。

                return 1;

        }

    }

    return 0;

}

int main()

{

    scanf("%d",&n);

    char s[maxn];

    for(int i = 1; i<=n; i++)

    {

        scanf("%s",s+1);

        for(int j = 1; j<=n; j++)

            g[i][j] = s[j] - '0';

    }

    for(int i = 1; i<=n; i++)

        if(!vis[i] && dfs(i,-1))

            return 0;

    puts("-1");

    return 0;

}

巴特西

Codeforces Beta Round #88 C. Cycle —— DFS（找环）

最新文章

热门文章