法1 : 并查集
根据题目要求可以看出是一道考察并查集的题目,直接套用模板,最后检查一下是否全部联通就好
代码
#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int n, m;
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool check()
{
int cnt = 0;
for(int i = 1; i <= n; i ++)
if(p[i] == i) cnt ++;
return cnt == 1;
}
int main()
{
while(cin >> n >> m)
{
for(int i = 1; i <= n; i ++) p[i] = i;
while(m --)
{
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
p[a] = b;
}
if(check()) puts("YES");
else puts("NO");
}
return 0;
}
法2 :最短路
我用的是Dijkstra求,我们假定1为源点,只要有一个点不可抵达,那么就不连通
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, M = 5e4 + 10, inf = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int dis[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dij()
{
memset(dis, inf, sizeof dis);
dis[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, 1});
while(q.size())
{
auto t = q.top();
q.pop();
int ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dis[j] > dis[ver] + 1)
{
dis[j] = dis[ver] + 1;
q.push({dis[j], j});
}
}
}
}
bool check()
{
for(int i = 2; i <= n; i ++)
if(dis[i] == inf) return false;
return true;
}
int main()
{
while(scanf("%d%d", &n, &m) != -1)
{
memset(h, -1, (n + 1) * 4);
memset(st, false, (n + 1) * 4);
idx = 0;
while(m --)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dij();
if(check()) puts("YES");
else puts("NO");
}
return 0;
}