codeforces 1708E - DFS Trees

E - DFS Trees

Portal

prob.: Give me a n spot m Undirected graph of edges and a wrong solution MST Code for , Ask which points are the roots MST That's right.

ideas: There is no edge with equal weight , combination MST The nature of , When there is a ring ,MST Always round off the largest edge in the ring

Consider that each point on the ring is the first point traversed by the algorithm given by the question in the point set on the ring , It is found that only when this point is the endpoint of the largest edge （ This is the picture 1 Medium u or v）

Consider the whole picture , Some points as a starting point must be illegal （ On the division ring u,v The direction of other points （ To put it another way, only u,v And their non ring direction is feasible （ This is the picture 1 Part of the middle green circle ）

Consider marking points -> Dyeing on trees -> The difference in the tree （ Refer to Xinjun b Station video solution ）

In the right MST Build up trees , The largest edge of each ring is not MST On the edge of

For each point, if point weight >0, Indicates that it has been marked , That is, it is an illegal point in at least one ring

Consider two situations （ Pictured 2 Shown ）

1. u,v Of lca No u or v, Consider the weight of the whole number ++ then u,v Weight of subtree –
2. u,v Of lca yes u or v, set up lca==u, Consider for u My son's weight ++,v Weight of subtree –

code：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

vector<int> g[N];
int pa[N], depth[N], f[N][30];
int a[N], b[N];

int Find(int x) {
    
    if (pa[x] == x) return x;
    return pa[x] = Find(pa[x]);
}

void Union(int x, int y) {
    
    int fax = Find(x);
    int fay = Find(y);
    if (fax == fay) return;
    pa[fax] = fay;
}

struct edge {
    
    int u, v;
};

vector<edge> edges, vec;

void bfs(int rt) {
    
    queue<int> que;
    que.push(rt);
    while (!que.empty()) {
    
        int tmp = que.front();
        que.pop();
        for (auto u : g[tmp]) {
    
            if (u == pa[tmp]) continue;
            depth[u] = depth[tmp] + 1;
            que.push(u);
            f[u][0] = pa[u];
            for (int k = 1; k < 20; ++k) {
    
                f[u][k] = f[f[u][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; --k) {
    
        if (depth[f[a][k]] >= depth[b]) {
    
            a = f[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 19; k >= 0; --k) {
    
        if (f[a][k] != f[b][k]) {
    
            a = f[a][k];
            b = f[b][k];
        }
    }
    return f[a][0];
}

int getPa(int x, int num) {
    
    for (int k = 19; k >= 0; --k) {
    
        if ((num >> k) & 1) x = f[x][k];
    }
    return x;
}

void dfs(int x, int sum){
    
    a[x] = sum + b[x];
    for(auto to : g[x]) {
    
        if(to == pa[x]) continue;
        dfs(to, a[x]);
    }
}

void dfsPa(int x) {
    
    for(auto to : g[x]) {
    
        if(to == pa[x]) continue;
        pa[to] = x;
        dfsPa(to);
    }
}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) pa[i] = i;
    for (int i = 1; i <= m; ++i) {
    
        int u, v;
        cin >> u >> v;
        edges.push_back({
    u, v});
    }

    for (auto tt :edges) {
    
        int u = tt.u;
        int v = tt.v;
        if (Find(u) == Find(v)) {
    
            vec.push_back(tt);
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
        Union(u, v);
    }

    int rt = 1;
    pa[rt] = -1;
    dfsPa(rt);
    depth[rt] = 1, depth[0] = 0;
    pa[rt] = 0;
    bfs(rt);

    for (auto tt : vec) {
    
        int u = tt.u;
        int v = tt.v;
        if (lca(u, v) != u && lca(u, v) != v) {
    
            b[rt]++;
            b[u]--;
            b[v]--;
        } else {
    
            if (lca(u, v) == v) swap(u, v);
            int s = getPa(v, depth[v] - depth[u] - 1);
            b[s]++;
            b[v]--;
        }
    }

    dfs(rt, 0);

    for (int i = 1; i <= n; ++i) {
    
        cout << (a[i] > 0 ? 0 : 1);
    }
    return 0;
}