581 week10

max component.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 55555;
vector<int> g[N];

void dfs(int u, bool seen[], int w[], int &ans)
{
    if (seen[u])
        return;
    seen[u] = true;
    ans += w[u];

    for (auto v : g[u]) {
        dfs(v, seen, w, ans);
    }
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        int n, m;
        scanf("%d %d", &n, &m);

        int w[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &w[i]);
            g[i].clear();
        }

        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }

        bool seen[N] = {false};
        int mx = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (seen[i] == false) {
                int sum = 0;
                dfs(i, seen, w, sum);
                mx = max(mx, sum);
            }
        }

        printf("%d\n", mx);
    }

    return 0;
}

spy.cpp

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);

    // read input
    int par[n];
    par[0] = -1;
    for (int i = 1; i < n; i++)
        scanf("%d", &par[i]);

    int ans = 0;
    // traverse from the back of the list -> start from the leaf
    for (int i = n - 1; i > 0; i--) {
        if (par[i] >= 0) { // if the current leaf node has a parent
            ans++; // let's select this node's parent as a node for monitoring

            for (int j = 1; j < n; j++) {
                // we erase all children of the node we just selected (set to -1)
                if (i != j && par[j] == par[i]) {
                    par[j] = -1;
                }
            }

            if (par[i] != 0)
                par[par[i]] = -1;
            par[i] = -1;
        }
    }

    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--)
        solve();

    return 0;
}

線段覆蓋長.cpp

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

void solve()
{
    int n;
    scanf("%d", &n);

    ii inp[n];
    for (int i = 0; i < n; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        inp[i] = ii(s, t);
    }
    sort(inp, inp + n);

    int cur_s = 0, cur_t = 0;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (inp[i].first < cur_t) {
            // extension
            cur_t = max(cur_t, inp[i].second);
        } else {
            ans += cur_t - cur_s;
            cur_s = inp[i].first;
            cur_t = inp[i].second;
        }
    }

    ans += cur_t - cur_s;
    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--)
        solve();

    return 0;
}