Với một đồ thị bất kì, nếu 2 trong 3 mệnh đề sau là đúng, thì mệnh đề còn lại là đúng:
Đồ thị liên thông
Đồ thị không có chu trình
Số đỉnh của đồ thị lớn hơn số cạnh của đồ thị đúng 1 đơn vị
Điều đó có nghĩa là, chỉ cần thỏa 2 trong 3 điều kiện đó thì đồ thị chắc chắn sẽ là một cây, và cây đó sẽ thỏa cả 3 điều kiện trên (trừ cây rỗng - cây không có đỉnh nào).
Source: [Cây(Tree)-VNOI WIKI](https://wiki.vnoi.info/translate/wcipeg/tree).
Vậy để giải quyết bài toán này ta cần kiểm tra đồ thị có đủ 2 trong 3 mệnh đề hay chưa?
Đầu tiên ta đã có đỉnh và cạnh của đồ thị là m,n nên điều kiện 3 là dễ kiểm tra nhất
Tiếp theo ta kiểm tra đồ thị có liên thông hay không hoặc đồ thị có chu trình hay không?Lời giải sau kiểm tra điều kiện 1 tuy nhiên bạn vẫn có thể kiểm tra bằng điều kiện 2.
Cuối cùng nếu thỏa mãn cả 2 điều kiện (1,3) hoặc (2,3) mà bạn kiểm tra thì đồ thị là cây.
**Lưu ý: Sau đây là code mẫu, chỉ xem khi thật sự cần thiết**
```
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> adj[100001];
bool visited[100001];
void inp()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
memset(visited,false,sizeof(visited));
}
void dfs(int u)
{
visited[u]=true;
for(int x:adj[u])
{
if(!visited[x]) dfs(x);
}
}
void connectedComponent()
{
int ans=0;
for(int i=1;i<=n;i++)
{
if(!visited[i])
{
++ans;
dfs(i);
}
}
if((n-m==1)&&(ans==1))
cout<<"YES";
else cout<<"NO";
}
int main()
{
inp();
connectedComponent();
return 0;
}
```
Kaizen
Created at
1 likes