codeforces 456 E. Civilization（并查集+数的直径）

题目链接：http://codeforces.com/contest/456/problem/E

题意：给出N个点，M条边，组成无环图（树），给出Q个操作，操作有两种：

1 x，输出x所在的联通块的最长路；

2 x y，若x和y在同一联通块，则不操作；若不在同一联通块，则选择这两个联通块的各一个城市连一条边，使新的联通块的最长路最短，若有多种选择则随便选。

题解：就是先求出一开始几个连通块的最长路，然后之后q个操作没必要真正意义上连边，只要用并查集更新一下就行了，最后代码有些事要优化的具体看一下代码。

还有求最长路就是求数的直径就行，树的直径就是两遍dfs or bfs。

#include <iostream>

#include <queue>

#include <cstring>

#include <cstdio>

using namespace std;

const int M = 3e5 + 10;

int f[M] , dis[M] , head[M] , e;

void init(int n) {

    for(int i = 1 ; i <= n ; i++) f[i] = i;

    memset(dis , 0 , sizeof(dis));

    memset(head , -1 , sizeof(head));

    e = 0;

}

struct Edge {

    int u , v , next;

}edge[M << 1];

void add(int u , int v) {

    edge[e].v = v;

    edge[e].next = head[u];

    head[u] = e++;

}

int find(int x) {

    if(x == f[x]) return x;

    int tmp = find(f[x]);

    return f[x] = tmp;

}

struct TnT {

    int pos , step;

    TnT(){}

    TnT(int pos , int step):pos(pos) , step(step) {}

};

bool vis[M] , vs[M];

int maxi , maxd , father;

void dfs(int u , int pre , int step) {

    f[u] = father;

    if(step > maxd) {

        maxd = step;

        maxi = u;

    }

    for(int i = head[u] ; i != -1 ; i = edge[i].next) {

        int v = edge[i].v;

        if(v == pre) continue;

        dfs(v , u , step + 1);

    }

}

int main() {

    int n , m , q;

    scanf("%d%d%d" , &n , &m , &q);

    init(n);

    for(int i = 0 ; i < m ; i++) {

        int u , v;

        scanf("%d%d" , & u , &v);

        add(u , v);

        add(v , u);

        //一开始的时候先不要直接并查集如果一开始就并查集的话后面就一定会用到find函数，这样会超时的。

    }

    for(int i = 1 ; i <= n ; i++) {

        if(f[i] == i) {

            father = i;

            //在求最长路的同时进行并查集，父节点全都定为i这样就不会超时了。优化就在这里，稍微注意一下就行。

            maxd = -1;

            dfs(i , -1 , 0);

            maxd = -1;

            dfs(maxi , -1 , 0);

            dis[i] = maxd;

        }

    }

    while(q--) {

        int x , y , t;

        scanf("%d" , &t);

        if(t == 1) {

            scanf("%d" , &x);

            int gg = find(x);

            printf("%d\n" , dis[gg]);

        }

        else {

            scanf("%d%d" , &x , &y);

            int a = find(x) , b = find(y);

            if(a == b) continue;

            else {

                f[a] = b;

                dis[b] = max(max(dis[a] , dis[b]) , (dis[a] + 1) / 2 + (dis[b] + 1) / 2 + 1);

                //两个连通块连在一起怎么使得连在一起后使得这个连通块的最长路尽量的短，那么显然要中点和中点连在一起。

            }

        }

    }

    return 0;

}

巴特西

codeforces 456 E. Civilization（并查集+数的直径）

最新文章

热门文章