Advertisement
anas_harby

Untitled

Jul 13th, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, m;
  6. vector <int> edges[100010];
  7. bool visited[100010], f = false;
  8.  
  9. void DFS(int vertix, int prev) {
  10.     visited[vertix] = true;
  11.     for (int i = 0; i < edges[vertix].size(); i++) {
  12.         if (!visited[edges[vertix][i]]) {
  13.             DFS(edges[vertix][i], vertix);
  14.         } else if (edges[vertix][i] != prev) {
  15.             f = true;
  16.         }
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     cin >> n >> m;
  23.     for (int i = 0; i < m; i++) {
  24.         int x, y;
  25.         cin >> x >> y;
  26.         x--, y--;
  27.         edges[x].push_back(y), edges[y].push_back(x);
  28.     }
  29.     int res = 0;
  30.     for (int i = 0; i < n; i++) {
  31.         if (!visited[i]) {
  32.             f = false;
  33.             DFS(i, -1);
  34.             if (!f)
  35.                 res++;
  36.         }
  37.     }
  38.     cout << res;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement