题目:Codeforces Round #260 (Div. 2) E. Civilization
题意:输入n,m,q,n代表点数,m是边数,q是问题数。问题有两种一种是链接两个集合使得合并后的最长路径最短,另一种是求某个集合的最长路径长度。
思路:据说这个叫树的直径,求法就是两次dfs。要合并后的直径最短,合并点一定是两个集合最长链的中点。
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <set> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back #define maxint 0x7fffffff const int maxn = 300010; vector <int> G[maxn]; int diameter[maxn]; int parent[maxn]; int vis[maxn]; int NODE, dep; int getSet(int x){ return parent[x] = x == parent[x] ? x : getSet(parent[x]); } int mergSet(int x, int y){ x = getSet(x); y = getSet(y); if( x > y ) swap(x,y); parent[y] = x; } int dfs(int x, int d, int p){ // cout << x << ' ' << d << endl; if( d > dep) { dep = d; NODE = x; } for(int i = 0; i < G[x].size(); i ++){ // cout << "ok" << endl; // system("pause"); if( G[x][i] != p) dfs(G[x][i], d+1, x); } } void solve(int n){ for(int i = 1; i <= n; i ++) if(!vis[getSet(i)]){ dep = -1; dfs(i, 0, -1); dfs(NODE, 0, -1); // cout << dep << endl; vis[getSet(i)] = 1; diameter[getSet(i)] = dep; } } void init(int n){ for(int i = 0; i <= n; i ++) { parent[i] = i; diameter[i] = 0; G[i].clear(); vis[i] = 0; } } int main(){ int n, m, q; int from, to, x; scanf("%d%d%d",&n,&m,&q); init(n); for(int i = 0; i < m; i ++) { scanf("%d%d",&from,&to); G[from].push_back(to); G[to].push_back(from); mergSet(from, to); } solve(n); while(q--){ scanf("%d",&x); if( x == 1) { scanf("%d",&from); printf("%d\n",diameter[getSet(from)]); } else { scanf("%d%d",&from,&to); from = getSet(from); to = getSet(to); if( from == to ) continue; int newdia = max(diameter[from], diameter[to]); newdia = max(newdia, (diameter[from]+1)/2+(diameter[to]+1)/2+1); mergSet(from, to); diameter[getSet(from)] = newdia; } } return 0; }