Algorithms/MVC.cpp at master · asimali246/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <cstring>
#include <iomanip>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <vector>
#include <new>
#include <bitset>
#include <ctime>
#include <stdint.h>
#include <unistd.h>

 using namespace std;

#define ll long long int
#define INF 2147483647
#define PI acos(-1.0)
#define EPS 1e-9

template <typename X> X gcd(X a, X b){if(!b)return a; else return gcd(b, a%b);}

typedef vector<int> vi;
typedef pair<int, int> ii;

const int N = 1<<17;
int n, i, u, v, dp[N][2], vis[N];
vector<int> g[N];

int MVC(int u, int flag) {
    if(dp[u][flag] != -1)
        return dp[u][flag];
    if((int)g[u].size() == 1 && u != 1)
        return flag;
    vis[u] = 1;
    int ans = flag;
    if( !flag ) {
        for( int j = 0; j < (int) g[u].size(); ++j )
            if( !vis[g[u][j]] )
                ans += MVC(g[u][j], 1);
    }
    else
        for( int j = 0; j < (int) g[u].size(); ++j )
            if( !vis[g[u][j]] )
                ans += min( MVC(g[u][j], 0), MVC(g[u][j], 1) );
    vis[u] = 0;
    return dp[u][flag] = ans;
}

int main() {
    scanf("%d", &n);
    for( i = 1; i <= n; ++i )
        g[i].clear(), dp[i][0] = dp[i][1] = -1;
    for( i = 1; i < n; ++i ) {
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if( n == 1 )
        printf("1\n");
    else
        printf("%d\n", min( MVC(1, 0), MVC(1, 1) ));
    return 0;
}