BOJ 2533 사회망 서비스(SNS)

1 개요

BOJ 2533 사회망 서비스(SNS)

• 백준 온라인 저지 2533번 문제
• BOJ 38단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> edges[1000001];
bool visited[1000001];
int dp[1000001][2];

void Find(int x) {
    visited[x] = true;
    dp[x][0] = 1;
    for (int i = 0; i < edges[x].size(); i++) {
        int child = edges[x][i];
        if (visited[child]) continue;
        Find(child);
        dp[x][1] += dp[child][0];
        dp[x][0] += min(dp[child][1], dp[child][0]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    int u, v;
    for (int i = 0; i < N-1;i++){
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    Find(1);
    cout << min(dp[1][0], dp[1][1]);
}