方法一:dfs
深搜依次找到其他结点是否可以连通
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010 , M = 10010;
int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void dfs(int u,int father)
{
st[u] = 1;
for(int i = h[u]; ~ i ;i = ne[i])
{
int j = e[i];
if (j != father && !st[j]) //不能是该结点的父节点
dfs(j, u);
}
}
int main()
{
while(cin >> n >> m)
{
idx = 0;
int flag = 0;
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, -1);
for(int i = 1;i <= n;i ++)
if(!st[i])
flag = 1;
cout << (flag == 1 ? "NO" : "YES") << endl;
}
return 0;
}
方法二:并查集
依次判断每个结点的父节点是否相同
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int p[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;
while (m -- )
{
int a, b;
cin >> a >> b;
int fa = find(a), fb = find(b);
if(fa != fb)
p[fa] = fb;
}
int flag = 0;
int res = p[find(1)];
for(int i = 2;i <= n;i ++)
if(p[find(i)] != res)
{
flag = 1;
break;
}
cout << (flag == 1 ? "NO":"YES") << endl;
}
return 0;
}
图能用邻接矩阵存吗?
可以的,但是它的时间复杂度是O(n^2),会比用邻接表的O(m + n)慢很多
好的,谢谢
感觉dfs的传参只需要u就可以了,这里的father是为了防止回头吗(疑惑),但是每一次dfs都有st数组标记之前的点,可以保证已经搜过的点不会再搜。
嗯嗯 是的 其实只用传u参数就行 写的时候没注意hhh
orz