当前位置：首页 > news >正文

codeforces 455C 并查集

news 来源：原创 2024/4/27 16:31:41

传送门

给n个点，初始有m条边， q个操作。

每个操作有两种， 1是询问点x所在的连通块内的最长路径，就是树的直径。 2是将x, y所在的两个连通块连接起来，并且要合并之后的树的直径最小，如果属于同一个连通块就忽视这个操作。

先dfs出每个连通块的初始直径，然后合并的话就是len[x] = max( (len[x]+1)/2+(len[y]+1)/2+1, max(len[x], len[y])); 然后搞一搞就好了。

一开始写bfs写挫了一直超时，只好改成dfs......

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define pb(x) push_back(x)
  4 #define ll long long
  5 #define mk(x, y) make_pair(x, y)
  6 #define lson l, m, rt<<1
  7 #define mem(a) memset(a, 0, sizeof(a))
  8 #define rson m+1, r, rt<<1|1
  9 #define mem1(a) memset(a, -1, sizeof(a))
 10 #define mem2(a) memset(a, 0x3f, sizeof(a))
 11 #define rep(i, a, n) for(int i = a; i<n; i++)
 12 #define ull unsigned long long
 13 typedef pair<int, int> pll;
 14 const double PI = acos(-1.0);
 15 const double eps = 1e-8;
 16 const int mod = 1e9+7;
 17 const int inf = 1061109567;
 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 19 const int maxn = 3e5+5;
 20 int f[maxn], num[maxn], head[maxn*2], dis[maxn], cnt, q[maxn*2];
 21 struct node
 22 {
 23     int to, nextt;
 24 }e[maxn*2];
 25 void add(int u, int v) {
 26     e[cnt].to = v;
 27     e[cnt].nextt = head[u];
 28     head[u] = cnt++;
 29 }
 30 int findd(int u) {
 31     return f[u] == u?u:f[u] = findd(f[u]);
 32 }
 33 void unionn(int x, int y) {
 34     x = findd(x);
 35     y = findd(y);
 36     if(x == y)
 37         return ;
 38     f[y] = x;
 39     int now = (1+num[x])/2+(num[y]+1)/2+1;
 40     num[x] = max(now, max(num[x], num[y]));
 41 }
 42 int maxx = 0, pos = -1;
 43 int dfs(int u, int fa, int d) {
 44     if(d>maxx) {
 45         maxx = d;
 46         pos = u;
 47     }
 48     for(int i = head[u]; ~i; i = e[i].nextt) {
 49         int v = e[i].to;
 50         if(v == fa)
 51             continue;
 52         dfs(v, u, d+1);
 53     }
 54 }
 55 template<typename __ll>
 56 inline void read(__ll &m)
 57 {
 58     __ll x=0,f=1;char ch=getchar();
 59     while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
 60     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 61     m=x*f;
 62 }
 63 int main()
 64 {
 65     int n, m, q, x, y;
 66     cin>>n>>m>>q;
 67     mem1(head);
 68     for(int i = 1; i<=n; i++) {
 69         f[i] = i;
 70         num[i] = 0;
 71     }
 72     while(m--) {
 73         read(x); read(y);
 74         add(x, y);
 75         add(y, x);
 76         x = findd(x); y = findd(y);
 77         f[x] = y;
 78     }
 79     for(int i = 1; i<=n; i++) {
 80         if(f[i] == i) {
 81             dfs(i, -1, 0);
 82             maxx = 0;
 83             if(pos == -1)
 84                 continue;
 85             dfs(pos, -1, 0);
 86             num[i] = maxx;
 87             maxx = 0;
 88             pos = -1;
 89         }
 90     }
 91     while(q--) {
 92         int sign;
 93         read(sign);
 94         if(sign == 1) {
 95             read(x);
 96             printf("%d\n", num[findd(x)]);
 97         } else {
 98             read(x); read(y);
 99             unionn(x, y);
100         }
101     }
102 }