题目描述
给定一个无向图和其中的所有边,判断这个图是否所有顶点都是连通的。
输入格式
输入包含若干组数据。
每组数据第一行包含两个整数 n 和 m,表示无向图的点和边数。
接下来 m 行,每行包含两个整数 x,y,表示点 x 和点 y 相连。
点的编号从 1 到 n。
不保证没有重边和自环。
输出格式
每组数据输出一行,一个结果,如果所有顶点都是连通的,输出 YES,否则输出 NO。
数据范围
输入最多包含 10 组数据。
1≤n≤1000,
1≤m≤5000,
1≤x,y≤n
样例
输入样例:
4 3
1 2
2 3
3 2
3 2
1 2
2 3
输出样例:
NO
YES
算法1 并查集
(暴力枚举) 线性
这道题和4216类似
4216 : https://www.acwing.com/problem/content/4219/
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int p[N];
int n,m,cnt;
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main()
{
while(cin>>n>>m)
{
memset(p,0,sizeof p);
for (int i = 1; i <= n; i ++ )p[i]=i;
cnt = n;
while (m -- )
{
int a,b;
cin>>a>>b;
if(find(a)!=find(b))
{
cnt--;
p[find(a)]=find(b);
}
}
if(cnt==1)puts("YES");
else puts("NO");
}
return 0;
}
算法2
(暴力枚举)
链表存储
和4216不同的是,题目没要求只包含一个环,只要连通就行
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int e[N],ne[N],h[N],idx;
int st[N];
int n,m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa()
{
int sum = 0;
queue<int>q;
q.push(1);
st[1]=true;
while(q.size())
{
int t = q.front();
q.pop();
sum++;
for(int i = h[t]; ~i; i = ne[i] )
{
int j = e[i];
if(!st[j])
{
st[j]=true;
q.push(j);
}
}
}
if(sum==n)return true;
else return false;
}
int main()
{
while(cin>>n>>m)
{
int t = m;
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
while (m -- )
{
int a,b;
cin>>a>>b;
add(a, b);
add(b, a);
}
bool flag = spfa();
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
算法3 dfs
(暴力枚举)
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10;
bool st[N]; // g表示某两个点是否有边, st表示某个点是否被访问过
int n, m; // n个点 m条边
int h[N], e[N], ne[N], idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x)
{
st[x] = true; // 标记访问
for(int i = h[x];~i; i = ne[i])
{
int j = e[i];
if(!st[j]) dfs(j);
}
}
int main() {
while(cin >> n >> m){
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
for(int i = 0; i < m;i++) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1);
int cnt = 0;
for(int i = 1; i < N;i++)
if(st[i]) cnt++;
// cout << cnt << endl;
if(cnt == n) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}