首页 > 其他 > 详细

[8.16考试] 小皮的疑惑

时间:2018-08-16 16:13:36      阅读:311      评论:0      收藏:0      [点我收藏+]

Problem

伟大的哲学家小皮认为,友谊是具有传递性的:如果A和B存在一定的关系,B和C具有一定的关系,那么A和C之间也会有一定联系。
小皮喜欢研究他人的朋友圈,在他看来不满足上述关系的朋友圈都是不正常的朋友圈,可是人多起来关系也摸不清,请你来帮忙写一个程序检查该朋友圈是否正常.
假设一个朋友圈有N个人,M组关系,你需要检查是否对于任意一对有直接关系的A和B,B和C,都一定满足A和C有关系,如果A,C不存在直接关系则为不正常的朋友圈。
如果该朋友圈正常输出YES,否则输出NO。
本题为多测。

输入格式

多组测试数据.
第一行一个整数T,表示有T个朋友圈
接来下每组测试数据存在一个N,M . 表示有N个人,M组关系
接来下M行,每行两个正整数x,y,表示x和y存在直接关系,保证不存在重复的直接关系。

输出格式

包括T行,每一行一个YES或NO。

样例输入

4
4 3
1 3
3 4
1 4
4 4
3 1
2 3
3 4
1 2
10 4
4 3
5 10
8 9
1 2
3 2
1 2
2 3

样例输出

YES
NO
YES
NO

数据范围:\(n<=150000,m<=min(150000,\frac{n*(n-1)}{2})\)

Solution

看到连通性,容易想到是并查集,但应该如何判断是否在一个联通块内每两个点都联通呢?
无重边?显然只要统计一个点的度数就行了,若一个点的度数等于这个点所在的联通块的度数+1就行了。本题还是比较水的。
代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch<='9'&&ch>='0') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int du[201010],fa[200101],x[201010],y[201001],cnt[201010];
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
int main()
{
    freopen("friendship.in","r",stdin);
    freopen("friendship.out","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
        memset(du,0,sizeof(du));
        memset(cnt,0,sizeof(cnt));
        int n,m,flag=0;
        n=read();m=read();
        for(int i=1;i<=n;i++)
        fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            x[i]=read();y[i]=read();
            du[x[i]]++;du[y[i]]++;
            fa[find(x[i])]=find(y[i]);
        }
        for(int i=1;i<=n;i++)
        {
            int f1=find(i);
            cnt[f1]++;
        }
        for(int i=1;i<=n;i++)
        {
            int f1=find(i);
            if(!du[i]) continue;
            if(cnt[f1]!=du[i]+1)
            {
                flag=1;
                break;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
}

博主蒟蒻,可以随意转载,但必须附上原文链接k-z-j

[8.16考试] 小皮的疑惑

原文:https://www.cnblogs.com/kzj-pwq/p/9487835.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!