小y的旅行

题目描述

夏天的旅行是无限快乐，Alan想和自己最喜欢的小y开启旅程，可是小y却有着一些独自的看法！
Alan最近得到了一张London的地图，准备带着小y去旅行，其中详细标明了London内的n个景点，
其***有m条双向道路连接着这n个景点。但是由于小y的精力有限，她实在没有办法将n个景点全部都游览一
遍，于是只好算了一个她喜欢的数字k，她只想详细游览前k个景点，其他的等以后有机会再来。
受到了小y自己的困扰，小y特别害怕自己会在某个环上走来走去，她觉得这样的重复旅游去而导致可怕的事情发生，所以她希望
Alan能帮在地图上删去一些边，使得所有编号不大于k的所有景点都不在环上。

方法一：计算需要去掉的边

题目分析：题目要求的是使所有标号不大于k的所有景点都不在环上，那么我们可以先对起点和终点排序，把所有大号的都排在前面，然后我们利用并查集的思想，把这些点合并起来，如果两个点已经有公共祖先那么可以判断他们属于一个环上的点，如果这个环上的点有小于等于k的点，那么我们可以把这些边去掉。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int pre[maxn];

struct node
{
    int s, e;
    bool operator<(const node x) const
    {
        if (s != x.s)
            return s > x.s;
        return e > x.e;
    }
} w[maxn];
int find(int x)
{
    if (x != pre[x])
        pre[x] = find(pre[x]);
    return pre[x];
}
int main()
{
    int n, m, k;
    int ans = 0;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
        pre[i] = i;
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &w[i].s, &w[i].e);
    sort(w + 1, w + m + 1);
    for (int i = 1; i <= m; ++i)
    {
        if (find(w[i].s) == find(w[i].e))
        {
            if (min(w[i].s, w[i].e) <= k)
                ++ans;
        }
        else
            pre[find(w[i].s)] = find(w[i].e);
    }
    printf("%d\n", ans);
}

方法二：判断符合的边

我们首先判断如果两个点都大于k，那么这两个点形成的边是符合条件的，也就是不需要去掉的边，如果两个点不连通，那么就把它们连通起来，然后再遍历一次，如果两个点之间有小于等于k的点，并且他们不连通也就不符合提议条件，但是是不需要去掉的边，把它们加起来，然后使他们连通，最后用总的边数减掉不需要去掉的边就是符合题目要求的答案

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
int n, m, k, pre[maxn];
int find(int x)
{
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
void join(int x, int y)
{
    pre[find(x)] = find(y);
}
int u[maxn], v[maxn];
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i <= n; ++i)
        pre[i] = i;
    int ans = 0;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &u[i], &v[i]);
        if (u[i] > k && v[i] > k)
        {
            ans++;
            if (find(u[i]) != find(v[i]))
                join(u[i], v[i]);
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        if (min(u[i], v[i]) <= k)
        {
            if (find(u[i]) != find(v[i]))
            {
                ++ans;
                join(u[i], v[i]);
            }
        }
    }
    printf("%d\n", m - ans);
    return 0;
}