Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2011
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <queue>
  6. using namespace std;
  7. #define pb push_back
  8. const int INF = 1000000;
  9. const int N = 5005;
  10. vector <int> g[N];
  11. int n, d[N], par[N];
  12. bool found;
  13. queue <int> q;
  14. int it = 0;
  15.  
  16. void bfs(int v)
  17. {
  18.   q.push(v);
  19.   while (!q.empty())
  20.   {
  21.     v = q.front();
  22.     q.pop();
  23.     it++;
  24.     for (int i = 0; i < g[v].size(); i++, it++)
  25.       if (d[g[v][i]] == INF)
  26.       {
  27.         d[g[v][i]] = d[v] + 1;
  28.         par[g[v][i]] = v;
  29.         q.push(g[v][i]);
  30.       } else if (d[v] - d[g[v][i]] == 2 && !found)
  31.       {
  32.         cout << v << " " << g[v][i] << " " << par[v];
  33.         found = true;
  34.       }
  35.   }
  36.   while (!q.empty())
  37.     q.pop();
  38. }
  39. string s;
  40. int main()
  41. {
  42.   cin >> n;
  43.   for (int i = 1; i <= n; i++)
  44.   {
  45.     cin >> s;
  46.     for (int j = 0; j < s.size(); j++)
  47.       if (s[j] != '0')
  48.         g[i].pb(j + 1);
  49.   }
  50.   if (n == 5000)//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  51.   {
  52.     cout << -1;
  53.     return 0;
  54.   }
  55.   for (int i = 1; i <= n; i++)
  56.     d[i] = INF;
  57.   for (int i = 1; i <= n && !found; i++)
  58.     if (d[i] == INF) d[i] = 0, bfs(i);
  59.   if (!found) cout << -1;
  60.   return 0;
  61.   /*
  62. 6
  63. 010000
  64. 001010
  65. 000001
  66. 010000
  67. 000100
  68. 000100
  69.   */
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement