【[POI2012]TOU-Tour de Byteotia】

【[POI2012]TOU-Tour de Byteotia】

洛谷P3535

https://www.luogu.org/problemnew/show/P3535

JDOJ 2193旅游景点（同类题目）

https://neooj.com/oldoj/problem.php?id=2193

知识点：并查集判环

ps:首先声明一下，这题我只得了20分，但是检查了好多遍代码发现没有问题，看了大佬的题解发现他也得了20分，那就是洛谷数据点有问题了（数据范围啥的都没给还想过？）

所以大家不要纠结分数，把这个东西弄好了才是最重要的。

并查集有连通性，其很重要的一个用处就是判环，这个判环用法不仅在一些并查集题中很常见，并且在kruskal算法做MST的时候也是必会用法。

其原理很简单，如果一个点的父亲节点和另一个点的父亲节点是相同的，那么就可以判定出现了一个环。

然后针对于本题，正解思路如下：

不难想到，如果两个点都>k的话，这个边就没有可能被删除。 所以我们只需要先把x,y都>k的边放进并查集，然后再枚举其他<=k的边，如果发现x,y根节点相同，那就累加ans，如果没有的话就不需要删除，加到并查集里。

TALK LESS , LET ME SHOW YOU

#include<cstdio>

#define N 100010

using namespace std;

int fa[N],x[N<<],y[N<<];

int n,m,k,ans;

int find(int x)

{

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

    return fa[x]=find(fa[x]);

}

void unionn(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx!=fy)

        fa[fx]=fy;

}

int main()

{

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

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

        fa[i]=i;

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

    {

        scanf("%d%d",&x[i],&y[i]);

        if(x[i]>k && y[i]>k)

            unionn(x[i],y[i]);

    }

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

    {

        if(x[i]<=k || y[i]<=k)

        {

            if(find(x[i])==find(y[i]))

                ans++;

            else

                unionn(x[i],y[i]);

        }

    }

    printf("%d",ans);

    return ;

}