Advertisement
Josif_tepe

Untitled

Aug 13th, 2023
1,340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <fstream>
  8. using namespace std;
  9. typedef long long ll;
  10. const int maxn = 2e5 + 10;
  11. const int logn = 20;
  12. vector<int> graph[maxn];
  13. bool visited[maxn];
  14. int res;
  15. void dfs(int node, int prev) {
  16.     for(int i = 0; i < (int) graph[node].size(); i++) {
  17.         int neigh = graph[node][i];
  18.         if(neigh != prev) {
  19.             dfs(neigh, node);
  20.             if(!visited[neigh] and !visited[node]) {
  21.                 visited[neigh] = true;
  22.                 visited[node] = true;
  23.                 ++res;
  24.             }
  25.         }
  26.     }
  27. }
  28. int main() {
  29.     ios_base::sync_with_stdio(false);
  30.     int n;
  31.     cin >> n;
  32.     for(int i = 1; i < n; i++) {
  33.         int a, b;
  34.         cin >> a >> b;
  35.         graph[a].push_back(b);
  36.         graph[b].push_back(a);
  37.     }
  38.     res = 0;
  39.     memset(visited, 0, sizeof visited);
  40.     dfs(1, -1);
  41.     cout << res << endl;
  42.     return 0;
  43. }
  44.  
  45. // 200000
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement