图的直径习题题解

7680: 串串

题意

思路

• 图的直径问题。
• 将所有可以相互转换的 x, y 这两点连接起来，构成图。可以发现，这是一个森林，有多个连通分量，并且每个连通分量一定无环。
• 将题意转换为求所有连通分量的直径的最大值。
• 需要注意的是，如何求无向无环图的直径，以及如何标记已经访问过这个连通分量。

示例代码

#include<bits/stdc++.h>

using namespace std;

#define IOS cin.tie(nullptr) -> ios::sync_with_stdio(false)
#define ll long long
#define ull unsigned long long
//#define int ll
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define fer(i, m, n) for(int i = m; i < n; ++i)
#define ferd(i, m, n) for(int i = m; i >= n; --i)
#define dbg(x) cerr << #x << char(61) << x << " ###\n"
#define dbg_arr(a, i) cerr << #a << '[' << i << "]=" << a[i] << " ###\n";

#define lowbit(x)  ((x) & -(x))
#define popcount(x)  __builtin_popcount(x)
#define popcountll(x)  __builtin_popcountll(x)
#define clz(x)  __builtin_clz(x)
#define ctz(x)  __builtin_ctz(x)

using u32 = unsigned;
using i64 = ll;
using u64 = ull;
using i128 = __int128;
using u128 = unsigned __int128;

const int MOD = 1e9 + 7;
const int N = 5e4 + 2;
const int inf = 1e9;

vector<vector<int>> fac(N);

void init() {
	fer(i, 1, N) {
		for(int j = i * 2; j < N; j += i) {
			fac[j].push_back(i);
		}
	}
}

signed main() {
    IOS;

    init();
    int n;
    cin >> n;

    if(n == 1) {
    	cout << 0 << '\n';
    	return 0;
    } else if(n == 2) {
    	cout << 1 << '\n';
    	return 0;
    }

    vector<int> f(N);
    fer(i, 1, n + 1) f[i] = accumulate(all(fac[i]), 0);

    vector<bool> can(n + 1);
    fer(i, 1, n + 1) can[i] = f[i] < i;


    vector<vector<int>> g(n + 1);
    fer(i, 1, n + 1) {
    	if(can[i]) {
    		g[i].push_back(f[i]);
    		g[f[i]].push_back(i);
    	}
    }
    // 图是森林，总体不连通，每块连通分量无环
    // 求每块连通分量的直径

    // {最远点，距离}
    auto bfs = [&](int src) -> pii {
    	int far;
    	queue<int> q;
    	q.push(src);

	    vector<int> dist(n + 1, -1);
	    dist[src] = 0;
    	while(!q.empty()) {
    		int u = q.front(); q.pop();
    		for(auto v : g[u]) {
    			if(dist[v] == -1) {
    				// 不用取max的原因：无环
    				dist[v] = dist[u] + 1;
    				q.push(v);
    				far = v;
    			}
    		}
    	}
    	return {far, dist[far]};
    };

    vector<bool> vis(n + 1);
    int ans = 0;
    fer(i, 1, n + 1) {
    	// 标记连通块，每个连通块只访问一次
    	if(!vis[i]) {
    		vis[i] = true;
    		queue<int> q;
    		q.push(i);
    		vector<int> a = {i}; // 收集连通块的点
    		while(!q.empty()) {
    			int u = q.front(); q.pop();
    			for(int v : g[u]) {
    				if(!vis[v]) {
    					vis[v] = true;
	    				q.push(v);
	    				a.push_back(v);
    				}
    			}
    		}
    		if(a.size() == 1) continue;
    		pii p1 = bfs(i);
    		pii p2 = bfs(p1.first);
    		ans = max(ans, p2.second);
    	}
    }
    cout << ans << '\n';
    return 0;
}