Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define D 400007
- using namespace std;
- typedef long long ll;
- vector <ll> a[D], ta[D], ts;
- ll used[D], comp[D], ccount;
- void topsort(ll v)
- {
- used[v] = true;
- for (ll to : a[v])
- if (!used[to])
- topsort(to);
- ts.push_back(v);
- }
- void dfs(ll v)
- {
- comp[v] = ccount;
- for (ll to : ta[v])
- if (!comp[to])
- dfs(to);
- }
- void add(ll v1, ll v2)
- {
- a[v1].push_back(v2);
- ta[v2].push_back(v1);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- ll n, m, x1, x2;
- while (cin >> n >> m)
- {
- for (ll i = 0; i < D; i++)
- {
- a[i].clear();
- ta[i].clear();
- }
- ts.clear();
- memset(used, 0, sizeof(used));
- memset(comp, 0, sizeof(comp));
- ccount = 0;
- for (ll i = 1; i <= m; i++)
- {
- cin >> x1 >> x2;
- if (x1 < 0 && x2 < 0)
- {
- x1 = -x1; x2 = -x2;
- add(x1, x2 + n);
- add(x2, x1 + n);
- }
- if (x1 > 0 && x2 > 0)
- {
- add(x1 + n, x2);
- add(x2 + n, x1);
- }
- if (x1 < 0 && x2 > 0)
- {
- x1 = -x1;
- add(x1, x2);
- add(x2 + n, x1 + n);
- }
- if (x1 > 0 && x2 < 0)
- {
- x2 = -x2;
- add(x1 + n, x2 + n);
- add(x2, x1);
- }
- }
- topsort(1);
- if (used[1 + n])
- return cout << "no" << endl, 0;
- for (ll i = 2; i <= n * 2; i++)
- if (!used[i])
- topsort(i);
- reverse(ts.begin(), ts.end());
- for (ll v : ts)
- if (!comp[v])
- {
- ccount++;
- dfs(v);
- }
- for (ll i = 1; i <= n; i++)
- if (comp[i] == comp[i + n])
- return cout << "no" << endl, 0;
- cout << "yes" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement