Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<int> > g, gr;
- vector<char> used;
- vector<int> order, component;
- void dfs1(int v) {
- used[v] = true;
- for (size_t i = 0; i < g[v].size(); ++i)
- if (!used[g[v][i]])
- dfs1(g[v][i]);
- order.push_back(v);
- }
- void dfs2(int v) {
- used[v] = true;
- component.push_back(v);
- for (size_t i = 0; i < gr[v].size(); ++i)
- if (!used[gr[v][i]])
- dfs2(gr[v][i]);
- }
- int main() {
- int n, m, a, b, index_a, index_b, indexNot_a, indexNot_b;
- pair<int, int> kek;
- cin >> n >> m;
- n = n * 2;
- g.resize(n);
- gr.resize(n);
- vector<pair<int,int>> allVertexNotVertex;
- for (int i = 0; i < n; i+=2) {
- kek.first = i;
- kek.second = i + 1;
- allVertexNotVertex.push_back(kek);
- }
- for (int i = 0; i < m; i++) {
- cin >> a >> b;
- if (a < 0) {
- index_a = (-a * 2) - 1;
- indexNot_a = index_a - 1;
- } else {
- index_a = (a * 2) - 2;
- indexNot_a = index_a + 1;
- }
- if (b < 0) {
- index_b = (-b * 2) - 1;
- indexNot_b = index_b - 1;
- } else {
- index_b = (b * 2) - 2;
- indexNot_b = index_b + 1;
- }
- g[indexNot_a].push_back(index_b);
- gr[index_b].push_back(indexNot_a);
- g[indexNot_b].push_back(index_a);
- gr[index_a].push_back(indexNot_b);
- }
- used.assign(n, false);
- for (int i = 0; i < n; ++i)
- if (!used[i])
- dfs1(i);
- used.assign(n, false);
- for (int i = 0; i < n; ++i) {
- int v = order[n - 1 - i];
- if (!used[v]) {
- dfs2(v);
- sort(component.begin(), component.end());
- for (int j = 0; j < component.size() - 1; j++) {
- if (component[j + 1] - component[j] == 1) {
- kek.first = component[j];
- kek.second = component[j + 1];
- auto result1 = find(allVertexNotVertex.begin(), allVertexNotVertex.end(), kek);
- if (result1 != allVertexNotVertex.end()) {
- cout << "YES";
- return 0;
- }
- else
- continue;
- }
- }
- component.clear();
- }
- }
- cout << "NO";
- /*
- vector<bool> core(2*n, 0);
- vector<vector<bool>> graph(2*n, core);
- for (int i = 0; i < m; i++) {
- cin >> a >> b;
- if (a < 0) {
- index_a = (-a * 2) - 1;
- indexNot_a = index_a - 1;
- }
- else {
- index_a = (a * 2) - 2;
- indexNot_a = index_a + 1;
- }
- if (b < 0) {
- index_b = (-b * 2) - 1;
- indexNot_b = index_b - 1;
- }
- else {
- index_b = (b * 2) - 2;
- indexNot_b = index_b + 1;
- }
- graph[indexNot_a][index_b] = 1;
- graph[indexNot_b][index_a] = 1;
- }
- for (int i = 0; i < 2*n; i++) {
- for (int j = 0; j < 2*n; j++) {
- cout << graph[i][j] << " ";
- }
- cout << endl;
- }
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement