Codeforces 88 C: Cycles

gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
#include <set>

using namespace std;

typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;

bool marked[5024];
int pred[5024];
char mat[5024][5024];
AdjList adj;
bool dfs(int v) {
  marked[v] = true;
  for (EdgeList::iterator it = adj[v].begin();
      it != adj[v].end(); ++it) {
    if (marked[*it]) {
      // We have a cycle of three! Somewhere.
      // Unwind.
      vector<int> cycle;
      for (int i = v; i != *it; i = pred[i]) {
        cycle.push_back(i);
      }
      cycle.push_back(*it);
      reverse(cycle.begin(), cycle.end());
      // Three of these bastards form a cycle of three.
      for (int i = 0; i < cycle.size(); ++i) {
        // Is there a cycle centered here?
        int prev = cycle[(i+cycle.size()-1) % cycle.size()];
        int next = cycle[(i+1)%cycle.size()];
        if (mat[next][prev] == '1') {
          printf("%d %d %d\n", prev+1, cycle[i]+1, next+1);
          break;
        }
      }
      return true;
    } else {
      pred[*it] = v;
      if (dfs(*it)) return true;
    }
  }
  marked[v] = false;
  return false;
}

int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  
  int n;
  scanf("%d", &n);
  adj.resize(n);
  memset(pred, 0, sizeof(pred));
  memset(marked, 0, sizeof(marked));
  bool found[5024];
  memset(found, 0, sizeof(found));
  bool fail = true;
  for (int i = 0; i < n; ++i) {
    scanf("%s", mat[i]);
    int sum = 0;
    for (int j = 0; j < n; ++j) {
      sum += mat[i][j] - '0';
    }
    if (found[sum]) {
      fail = false;
    }
    found[sum] = true;
  }
  if (fail) {
    puts("-1");
  } else {
  for (int i = 0; i  < n; ++i) {

    for (int j = 0; j < n; ++j) {
      if (mat[i][j] == '1') {
        adj[i].push_back(j);
      }
    }
  }
  dfs(0);
  } 
  

  
  return 0;
}