bhupixb

Is it a tree

Jul 12th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.75 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 2e4;
  4. int vis[N], c = 0;
  5. vector < vector < int > > v(N);
  6.  
  7. void dfs(int root , int check){
  8. vis[root] = 1;
  9.  
  10. for(auto it : v[root]){
  11. if(!vis[it])dfs(it, root);
  12. else if(vis[it] && it != check){
  13. c = 1;
  14. return;
  15. }
  16. }
  17. }
  18. int main(){
  19. int i, l, r;
  20.  
  21. int n, m;
  22. cin >> n >> m;
  23. for( i = 0; i < m; i++){
  24. cin >> l >> r;
  25. v[l].push_back(r);
  26. v[r].push_back(l);
  27. }
  28. // for(i = 1; i <= n; i++)cout << parent[i] << ' ';cout << '\n';
  29. dfs(1,1);
  30. for(i = 1; i <= n; i++){
  31. if(!vis[i])c++;
  32. }
  33. // cout << c << endl;
  34. if(c || m != n-1)return cout << "NO",0;
  35. cout << "YES";
  36. }
Add Comment
Please, Sign In to add comment