LeetCode-Solutions/C++/minimum-edge-toggles-on-a-tree.cpp at master · kamyu104/LeetCode-Solutions · 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// Time:  O(n)
// Space: O(n)

// greedy, topological sort, bitmasks
class Solution {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<int> diff(n);
        for (int i = 0; i < n; ++i) {
            if (start[i] != target[i]) {
                diff[i] = 1;
            }
        }
        if (accumulate(cbegin(diff), cend(diff), 0) % 2) {
            return {-1};
        }
        vector<int> degree(n), adj(n), edge(n);
        for (int idx = 0; idx < size(edges); ++idx) {
            const auto& u = edges[idx][0], &v = edges[idx][1];
            ++degree[u];
            ++degree[v];
            adj[u] ^= v;
            adj[v] ^= u;
            edge[u] ^= idx;
            edge[v] ^= idx;
        }
        vector<bool> lookup(size(edges));
        for (int i = 0; i < n; ++i) {
            int u = i;
            while (degree[u] == 1) {
                const auto v = adj[u];
                const auto idx = edge[u];
                --degree[u];
                --degree[v];
                adj[u] ^= v;
                adj[v] ^= u;
                edge[u] ^= idx;
                edge[v] ^= idx;
                if (diff[u]) {
                    diff[u] ^= 1;
                    diff[v] ^= 1;
                    lookup[idx] = true;
                }
                u = v;
            }
        }
        vector<int> result;
        for (int i = 0; i < size(lookup); ++i) {
            if (lookup[i]) {
                result.emplace_back(i);
            }
        }
        return result;
    }
};

// Time:  O(n)
// Space: O(n)
// greedy, topological sort
class Solution2 {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<int> diff(n);
        for (int i = 0; i < n; ++i) {
            if (start[i] != target[i]) {
                diff[i] = 1;
            }
        }
        if (accumulate(cbegin(diff), cend(diff), 0) % 2) {
            return {-1};
        }
        vector<int> degree(n);
        vector<vector<pair<int, int>>> adj(n);
        const auto& topological_sort = [&]() {
            vector<bool> lookup(size(adj));
            vector<int> q;
            for (int u = 0; u < size(adj); ++u) {
                if (size(adj[u]) == 1) {
                    q.emplace_back(u);
                }
            }
            while (!empty(q)) {
                vector<int> new_q;
                for (const auto& u : q) {
                    for (const auto& [v, idx] : adj[u]) {
                        if (degree[v] == 0) {
                            continue;
                        }
                        --degree[u];
                        --degree[v];
                        if (degree[v] == 1) {
                            new_q.emplace_back(v);
                        }
                        if (diff[u]) {
                            diff[u] ^= 1;
                            diff[v] ^= 1;
                            lookup[idx] = true;
                        }
                    }
                }
                q = move(new_q);
            }
            return lookup;
        };

        for (int idx = 0; idx < size(edges); ++idx) {
            const auto& u = edges[idx][0], &v = edges[idx][1];
            ++degree[u];
            ++degree[v];
            adj[u].emplace_back(v, idx);
            adj[v].emplace_back(u, idx);
        }
        const auto& lookup = topological_sort();
        vector<int> result;
        for (int i = 0; i < size(lookup); ++i) {
            if (lookup[i]) {
                result.emplace_back(i);
            }
        }
        return result;
    }
};