题解 SP131 【SQDANCE - Square dance】

jiangxt · 2019-01-27 11:35:50 · 题解

这是一道裸题。

蒟蒻觉得题目可以这么理解：有T队数据（不解释） 每组数据都是一个集合，一开始集合为空，每次你会得到一对质数，如果集合中存在若干个数对，将这些数对和你得到的数对中所有的数乘起来是完全平方数，那么就将这个数对扔掉，否则就将这个数对加入集合。最后输出扔掉的数的对数。

由于素数本身是什么并不重要，题中就只给出了素数的编号，编号相同的素数即为同一个素数

而要是平方数，就是有两个相同的素数相乘。

因此，可意建一个链表，每当给一对是，就判断它们是否在一个链表中。若是，这删除这对数。若不是，就将这对数加入链表。

附上代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,a[200001];//s为删除的对数
struct each
{
    int x,y;
}b[200001];

int find(int x)//寻找是否在一个链表中
{
    if(a[x]==0)
        return x;
    a[x]=find(a[x]);
    return a[x];
}
int read() 
{
    register int ans=0;register char c=getchar();register bool neg=0;
    while((c<'0')|(c>'9')) neg^=!(c^'-'),c=getchar();
    while((c>='0')&(c<='9')) ans=(ans<<3)+(ans<<1)+(c^'0'),c=getchar();
    return neg?-ans:ans;
}

int main()
{
    t=read();
    for(int k=1;k<=t;++k)
    {
        s=0;
        memset(a,0,sizeof(a));
        n=read();
        m=read();
        for(int i=1;i<=m;i++)
        {

            b[i].x=read();
            b[i].y=read();
        }

        for(int i=1;i<=m;i++)
        {
            int X=find(b[i].x),Y=find(b[i].y);
            if(X!=Y)//判断是否属于一个链表
                a[X]=Y;
            else
                ++s;    
        }
        printf("%d\n",s);
    }
    return 0;
}