A. 美麗子圖 (Beautiful Subgraph) 題解

直接暴力用並查集判斷是

$\mathcal{O}(N^2)$
用並查集加 pointer 判斷有多少已經跟

$0$ 連通是

$\mathcal{O}(N\lg N+N)$ 或

$\mathcal{O}(N\alpha (N)+N)$
用 dfs 判斷能否抵達所有編號

$\le i$ 的點是

$\mathcal{O}(N)$

這題用

$\mathcal{O}(N\lg N)$ 就可以過了，測資沒有卡複雜度比較大的作法的原因是我不會壓常 QQ

官方解答 by Yojahuang

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2000005;

int n, m, dis[MAXN], sz[MAXN], cnt;
bool vis[MAXN];
vector<int> G[MAXN];

void init() {
    for (int i = 0; i < n; ++i) {
        G[i].clear();
        dis[i] = i;
        vis[i] = false;
        sz[i] = 1;
    }
    cnt = 1;
}

int fa(int id) {
    if (dis[id] != id) dis[id] = fa(dis[id]);
    return dis[id];
}

void Un(int a, int b) {
    a = fa(a); b = fa(b);
    if (a == b) return ;

    sz[b] = sz[a] + sz[b];
    dis[a] = b;

    cnt = max(cnt, sz[b]);
}

void upd(int id) {
    vis[id] = true;
    for (auto x : G[id]) {
        if (vis[x]) Un(id, x);
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    while (cin >> n >> m) {
        init();
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            G[v].push_back(u);
            G[u].push_back(v);
        }

        for (int i = 0; i < n; ++i) {
            upd(i);

            if (cnt == i+1) cout << "1";
            else cout << "0";
        }
        cout << '\n';
    }

    return 0;
}

官方解答 dsu with pointer

#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int MAXN = 1E6;
const int maxn = 2E6 + 5;

vector<int> adj[maxn];
int p[maxn];
char ans[maxn];

int R(int x) {
    return x ^ p[x] ? p[x] = R(p[x]) : x;
}

int U(int x, int y) {
    if (R(x) == R(y)) return 0;
    p[p[x]] = p[y]; return 1;
}

int32_t main() {
    // fastIO();
    
    int n, m, u, v, ptr = 0;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i <= n; ++i) p[i] = i;
    
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &u, &v);
        if (u < v) swap(u, v);
        adj[u].emplace_back(v);
    }
    
    for (int i = 0; i < n; ++i) {
        for (auto x : adj[i]) U(i, x);
        while (R(ptr) == R(0)) ++ptr;
        ans[i] = (ptr > i ? '1' : '0');
    }
    
    ans[n] = '\0';
    printf("%s\n", ans);
    
    return 0;
}

官方解答 dfs with pointer

#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int MAXN = 1E6;
const int maxn = 2E6 + 5;

int lim, cnt;
int vis[maxn]; /// 0 for not visited, 1 for visited, 2 for in-queue
char ans[maxn];
vector<int> adj[maxn];

void dfs(int now) {
    for (auto x : adj[now]) {
        if (vis[x] == 1) continue;
        vis[x] = 2;
        if (x <= lim) ++cnt, vis[x] = 1, dfs(x);
    }
}

int32_t main() {
    // fastIO();
    
    int n, m, u, v;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &u, &v);
        if (u == v) continue;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vis[0] = 1;
    for (int i = 0; i < n; ++i) {
        if (vis[i]) {
            lim = i, ++cnt, vis[i] = 1, dfs(i);
            ans[i] = (cnt == i + 1 ? '1' : '0');
        }
        else ans[i] = '0';
    }
    
    ans[n] = '\0';
    printf("%s\n", ans);
    
    return 0;
}