前置知识:最小生成树
算法1
根据最小生成树,我们可知:n个点连在一起要n-1条边(这些边不能连已经在一个块内的边)
所以我们只要看这m条边中是否存在这样的n-1条边
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,m,fa[1005],sum,x,y,xx,yy;
int afind(int x){return x==fa[x]?x:fa[x]=afind(fa[x]);}
int main()
{
while(cin>>n>>m)
{
sum=0;
for(int i=1;i<=n;i++)fa[i]=i;
while(m--)
{
cin>>x>>y;
xx=afind(x);yy=afind(y);
if(xx!=yy)//存在这样的边,边数+1
{
fa[xx]=yy;
sum++;
}
}
if(sum==n-1)//判断
puts("YES");
else puts("NO");
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla