스터디 23/01/14 2533 : 사회망 서비스(SNS)

2533번: 사회망 서비스(SNS) (acmicpc.net)

2533번: 사회망 서비스(SNS)

풀이
1. 특정 부모 노드를 기준으로 모든 자식이 모두 얼리아답터가 아닌 이상 해당 부모가 얼리아답터인것이 유리하다.
  1) 자식 노드들이 모두 리프노드라면 한 명의 부모로 나머지 자식들이 아이디어를 받아들일 수 있다. (1 : N)
  2) 해당 노드가 얼리아답터라면 노드의 부모는 얼리아답터가 아닐 확률이 상대적으로 높아진다.

  3) 만약 자식 중 얼리아답터가 아닌 자식이 있다면 현재 노드가 얼리아답터가 아니라면 아이디어를 전파하는것이 불가능
2. 리프노드를 기준으로 DFS를 이용해 모든 자식노드가 얼리아답터라면 패스, 아니라면 현재 노드를 얼리아답타로 만든다.

 

시간복잡도 : O(n + n - 1), 노드의 개수 + 간선의 개수, n <= 1e6

#include<bits/stdc++.h>
#include<time.h>


#define MAX 5000001
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { -1, 0, 1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

vector<int> tree[1000001];
int cache[1000001];
int ans = 0;
int Dfs(int x) {
    if (tree[x].size() <= 1) {
        //cout << x<< " : " << 0 << "\n";
        return 0;
    }
    int ad = 0;
    for (int nx : tree[x]) {
        if (cache[nx]) continue;
        cache[nx] = 1;
        ad += Dfs(nx);
        cache[nx] = 0;
    }

    if (ad != tree[x].size() - 1) {
        ans++;
        //cout << x<< " : " << 1 << "\n";
        return 1;
    }
    else {
        //cout << x<<  " : " << 0 << "\n";
        return 0;
    }
}
int main() {
    init();
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    tree[1].push_back(0);
    cache[1] = 1;
    Dfs(1);
    cout << ans << "\n";
}