并查集
$O(n*logn)$
将所有联通的块组起来,则如果最大的块不是整幅图,那么这个图是不连通的。
问题迎刃而解,其他交给模板(并查集)
AC code
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010,M=5010;
int p[N],cnt[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,m;
while(cin>>n>>m)
{
for(int i=1;i<=n;i++) p[i]=i,cnt[i]=1;
while(m--)
{
int a,b; cin>>a>>b;
int x=find(a),y=find(b);
if(x!=y)
{
p[x]=y;
cnt[y]+=cnt[x];
}
}
puts(cnt[find(1)]==n?"YES":"NO");
}
return 0;
}
他这个输入组数不确定,第一个循环怎么跳出来的
系统给出的输入文件最后是有一个^z的,这个的作用就是停止输入。所以在判断输入流的时候读到这一句可以自动退出。(^z就是俗话说的ctrl+z)
嗯,谢谢。我在本地自己输入数据测试不过以为就不行,哈哈
最后可以用
p[find(1)]==n
判断哦这样就不用定义res了能省两行
对滴!
那个应该是
cnt
不好意思打错了