Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<vector<int>> graph;
- void dfs(int v, int num) {
- color[v] = num;
- for (int to : graph[v]) {
- if (color[to] == 0) {
- dfs(to, (num * -1));
- } else if (color[to] == num) {
- cout << "NO" << endl;
- exit(0);
- }
- }
- }
- int main() {
- int n, m, a, b;
- cin >> n >> m;
- graph.resize(n + 1);
- color.assign(n + 1, 0);
- for (int j = 0; j < m; j++) {
- cin >> a >> b;
- --a;
- --b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- for (int i = 0; i < n; i++) {
- if (color[i] == 0) {
- dfs(i, 1);
- }
- }
- cout << "YES" << endl;
- }
Add Comment
Please, Sign In to add comment