F. 質數家族 (primeconn) －Subtask 1+2

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

vector<vector<int>> adj;
vector<int> vis;

void dfs(int now, int limit) {
    vis[now] = 1;
    for (int x : adj[now]) {
        if (!vis[x] and x <= limit) dfs(x, limit);
    }
}

bool isprime(int x) {
    for (int i = 2; i*i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return x != 1;
}

bool canconn(int p, int q) { /// p < q
    int len_p = 1, len_q = 1;

    if (p >=   10) ++len_p;
    if (p >=  100) ++len_p;
    if (p >= 1000) ++len_p;
    if (q >=   10) ++len_q;
    if (q >=  100) ++len_q;
    if (q >= 1000) ++len_q;

    if (len_q == len_p) {
        int diff = 0;
        while (p or q) {
            if (p % 10 != q % 10) ++diff;
            p /= 10, q /= 10;
        }
        return diff == 1;
    }

    if (len_q == len_p + 1) {
        if (len_q == 4) return p == q % 1000;
        if (len_q == 3) return p == q % 100;
        if (len_q == 2) return p == q % 10;
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N; cin >> N;

    adj.resize(N+5);
    vis.resize(N+5);

    vector<int> primes;
    for (int i = 1; i <= N; ++i) {
        if (isprime(i)) primes.emplace_back(i);
    }

    for (int p : primes) for (int q : primes) {
        if (p < q and canconn(p, q)) {
            adj[p].emplace_back(q);
            adj[q].emplace_back(p);
        }
    }

    int ans = 0;
    for (int p : primes) {
        fill(begin(vis), end(vis), 0);
        dfs(2, p);
        if (!vis[p]) ans += p;
    }
    cout << ans << "\n";

    return 0;
}