Algorithm

C. Cycle
time limit per test
2.5 seconds
memory limit per test
256 megabytes
Problem Link- https://codeforces.com/problemset/problem/117/C
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
Copy
5
00100
10000
01001
11101
11000
output
Copy
1 3 2
input
Copy
5
01111
00000
01000
01100
01110
output
Copy
-1



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <vector>


void dfs(long node, long from, const std::vector < std::vector<bool> > &g, std::vector<bool> &visited, std::vector<long> &cycle){

    if(visited[node]){return;}
    visited[node] = 1;
    if(cycle.size() > 0){return;}

    for(long u = 0; u < g[node].size(); u++){
        if(!g[node][u]){continue;}
        if((from >= 0) && g[u][from]){cycle.push_back(1 + from); cycle.push_back(1 + node); cycle.push_back(1 + u); return;}
        if(visited[u]){continue;}
        dfs(u, node, g, visited, cycle);
    }

    return;
}


int main(){

    std::ios_base::sync_with_stdio(false);
    long n; std::cin >> n; 
    std::vector < std::vector<bool> > g(n, std::vector<bool>(n, 0));

    for(long p = 0; p < n; p++){
        std::string s; std::cin >> s;
        for(long u = 0; u < n; u++){g[p][u] = s[u] - '0';}
    }

    std::vector<long> cycle;
    std::vector<bool> visited(n, 0);
    for(long p = 0; p < n; p++){
        if(visited[p]){continue;}
        dfs(p, -1, g, visited, cycle);
        if(cycle.size() > 0){break;}
    }

    if(cycle.size() >= 3){std::cout << cycle[0] << " " << cycle[1] << " " << cycle[2] << std::endl;}
    else{std::cout << "-1" << std::endl;}

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
00100
10000
01001
11101
11000

Output

x
–
+
cmd
1 3 2
Advertisements

Demonstration

Codeforces Solution-C. Cycle-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+