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就行了。本题还是比较水的。
代码如下：
```cpp
#include
#include
#include
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
");
else printf("YES
");
}
}
```
### 博主蒟蒻，可以随意转载，但必须附上原文链接[k-z-j](https://www.cnblogs.com/kzj-pwq/)。