Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- #include <queue>
- using namespace std;
- vector <bool> used;
- vector <bool> colour;
- void dfs(int v, vector <vector <int>> & a, bool col)
- {
- used[v] = true;
- colour[v] = !col;
- for (int i = 0; i < a[v].size(); i++)
- if (!used[a[v][i]])
- dfs(a[v][i], a, !col);
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m;
- cin >> n >> m;
- used.resize(n);
- colour.resize(n);
- vector <vector<int>> a(n);
- for (int j = 0; j < m; j++)
- {
- int u, v;
- cin >> u >> v;
- u--;
- v--;
- a[v].push_back(u);
- a[u].push_back(v);
- }
- for (int i = 0; i < n; i++)
- if (used[i] != true)
- dfs(i, a, false);
- for (int i = 0; i < n; i++)
- {
- cout << i << ": ";
- for (int j = 0; j < a[i].size(); j++)
- cout << a[i][j] << ' ';
- cout << endl;
- }
- for (int i = 0; i < colour.size(); i++)
- cout << (int)colour[i] << ' ';
- cout << endl;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < a[i].size(); j++)
- if (colour[i] == colour[a[i][j]])
- {
- cout << -1 << endl;
- return 0;
- }
- cout << "YES";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement