Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.80 KB | None | 0 0
  1. // Created by Manuver Gujjar on 25/09/19.
  2. // Copyright © 2019 Manuver Gujjar. All rights reserved.
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5.  
  6. vector<vector<int>> adj;
  7.  
  8. int dfs() {
  9. long n = adj.size();
  10. int start = 1;
  11. vector<bool> vis(n, false);
  12. vis[start] = true;
  13.  
  14. stack<pair<int, int>> s;
  15. s.push({start, 0});
  16. while(not s.empty()) {
  17. auto top = s.top();
  18. s.pop();
  19.  
  20. for(auto i : adj[top.first]) {
  21. if(vis[i] == true) {
  22. if(i == top.second) continue;
  23. return 0;
  24. }
  25. vis[i] = true;
  26. s.push({i, top.first});
  27. }
  28. }
  29. for(int i=1; i<n; i++) if(vis[i] == false) return 0;
  30. return 1;
  31. }
  32.  
  33. int main() {
  34. long n, m;
  35. cin >> n >> m;
  36. adj.resize(n + 1);
  37. for(int i=0; i<m; i++) {
  38. int a, b;
  39. cin >> a >> b;
  40. adj[a].push_back(b);
  41. adj[b].push_back(a);
  42. }
  43.  
  44. cout << (dfs() ? "YES\n" : "NO\n");
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement