树上行走

题目描述

牛牛苦练武功绝学——轻功水上漂，最终没有练成，但是他学会了在树上行走的本领。

这天，牛牛落入了敌人的陷阱，身后有巨石追击，面前有n个点，n-1条边连成一张连通图（一棵树），现在牛牛必须立马选择进入这张图中，但是牛牛发现，这张图有两种不同的点，一旦进入一个点，所有与该点不同类型的点都会消失（相连的边也会消失），牛牛只能走到有边相连的点，牛牛想要自己尽量有更多的点可以活动，那么他可以进入哪些点？

题目分析：因为在补其他题目的时候不小心看到这个题目考察的是并查集，但是不论我怎么想都不知道该怎么用并查集去解决这个问题，思考无果之后，我看了代码，代码带给我的震撼很大，并查集是我学习的第一个算法，但是这种解题思路却是我第一次见，这种思想，代码让人耳目一新，真的太爽了！！代码非常巧妙的运用并查集的思想解决了问题。

方法一：并查集

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn], f[maxn], b[maxn];

int find(int x) //寻找祖先
{
    if (x != f[x])
        f[x] = find(f[x]);
    return f[x];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        f[i] = i; //初始化元素
    }
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if (a[u] == a[v]) //把相同类型的元素合并起来
            f[find(u)] = find(v);
    }
    vector<int> v;
    vector<int>::iterator it;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        b[find(i)]++; //只对祖先元素进行加操作，同意一下联通个数
        ans = max(ans, b[find(i)]);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (b[find(i)] == ans) //如果某个元素与祖先相通那么就记录一下
            v.push_back(i);
    }
    printf("%d\n", v.size());
    for (it = v.begin(); it != v.end(); it++)
        printf("%d ", *it);
}

方法二：dfs+前向星存图

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int cnt, tot, pre[maxn], col[maxn], head[maxn], num, vis[maxn], ans;
struct node
{
    int to, nex;
} w[maxn];

void add(int a, int b) //前向星存边
{
    w[++cnt].to = b;
    w[cnt].nex = head[a];
    head[a] = cnt;
}

void dfs(int now)
{
    ++num;
    vis[now] = tot;                          //标记当前点已经走过，同时初始化
    for (int i = head[now]; i; i = w[i].nex) //遍历当前点的邻接点
    {
        int to = w[i].to;                    //记录当前点的下一个点
        if (!vis[to] && col[now] == col[to]) //如果当前点的下一个点没有被访问，并且两个点的类型相同
            dfs(to);                         //就遍历下一个点
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &col[i]);
    for (int i = 1; i < n; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
        add(b, a);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i]) //如果当前点没有被访问
        {
            ++tot, num = 0;
            dfs(i);         //递归遍历
            col[tot] = num; //把个点所能走到的最大的点的数量赋给数组
            ans = max(ans, num);
        }
    }
    int g = 0;
    for (int i = 1; i <= n; ++i)
        if (col[vis[i]] == ans) //如果当前点能到的点的数量等于最大值，那么说明当前点属于最大值的一部分
            pre[++g] = i;
    sort(pre + 1, pre + g + 1);
    printf("%d\n", g);
    for (int i = 1; i <= g; ++i)
        printf("%d%c", pre[i], i == g ? '\n' : ' ');
}