Advertisement
meriellez

Untitled

May 22nd, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8. int n;
  9. vector < vector<int> > g;
  10. vector<int> cl;
  11.  
  12. bool dfs (int v, int s) {
  13. cl[v] = 1;
  14. for (size_t i = 0; i < g[v].size(); i++) {
  15. int to = g[v][i];
  16. if (cl[to] == 0 && to != v && to != s) {
  17. if (dfs (to, v)) return true;
  18. }
  19. else if (cl[to] == 1 && to != v && to != s) {
  20. return true;
  21. }
  22. }
  23. cl[v] = 2;
  24. return false;
  25. }
  26.  
  27. int main() {
  28. int i, k = 0, m;
  29. cin >>n >>m;
  30. g.assign(n, vector <int>());
  31. cl.assign(n, 0);
  32. for(i = 0; i < m; i++){
  33. int x, y;
  34. cin >>x >>y;
  35. x--;
  36. y--;
  37. g[x].push_back(y);
  38. g[y].push_back(x);
  39. //cout <<g[x] <<' ' <<g[y] <<endl;
  40. }
  41. for (int i = 0; i < n; i++){
  42. if(cl[i] == 0){
  43. if (!dfs (i, -1)){
  44. k++;
  45. }
  46. }
  47. }
  48. if(k > 1){
  49. cout <<"A forest of " <<k <<" trees.";
  50. } else {
  51. if(k == 1){
  52. cout <<"There is one tree.";
  53. } else {
  54. cout <<"No trees.";
  55. }
  56. }
  57. return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement