Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdio>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define pb push_back
- const int INF = 1000000;
- const int N = 5005;
- vector <int> g[N];
- int n, d[N], par[N];
- bool found;
- queue <int> q;
- int it = 0;
- void bfs(int v)
- {
- q.push(v);
- while (!q.empty())
- {
- v = q.front();
- q.pop();
- it++;
- for (int i = 0; i < g[v].size(); i++, it++)
- if (d[g[v][i]] == INF)
- {
- d[g[v][i]] = d[v] + 1;
- par[g[v][i]] = v;
- q.push(g[v][i]);
- } else if (d[v] - d[g[v][i]] == 2 && !found)
- {
- cout << v << " " << g[v][i] << " " << par[v];
- found = true;
- }
- }
- while (!q.empty())
- q.pop();
- }
- string s;
- int main()
- {
- cin >> n;
- for (int i = 1; i <= n; i++)
- {
- cin >> s;
- for (int j = 0; j < s.size(); j++)
- if (s[j] != '0')
- g[i].pb(j + 1);
- }
- if (n == 5000)//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
- {
- cout << -1;
- return 0;
- }
- for (int i = 1; i <= n; i++)
- d[i] = INF;
- for (int i = 1; i <= n && !found; i++)
- if (d[i] == INF) d[i] = 0, bfs(i);
- if (!found) cout << -1;
- return 0;
- /*
- 6
- 010000
- 001010
- 000001
- 010000
- 000100
- 000100
- */
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement