💡 Mô tả cách giải:
- Đầu vào là một đồ thị vô hướng có n đỉnh và m cạnh.
- Ta dùng DFS (tìm kiếm theo chiều sâu) để duyệt đồ thị.
- Mỗi lần bắt đầu DFS từ một đỉnh chưa được thăm, ta coi như đã tìm được một thành phần liên thông mới.
- Kết quả là số lần bắt đầu DFS từ các đỉnh chưa thăm, chính là số thành phần liên thông trong đồ thị.
🧠 Ý tưởng chính:
- Duyệt từng đỉnh từ 1 đến n.
- Nếu đỉnh đó chưa được thăm, thực hiện DFS từ đỉnh đó.
- Mỗi lần như vậy, tăng biến đếm cnt lên 1.
- Cuối cùng, in ra cnt.
**Code:**
```
#include <bits/stdc++.h>
#define ll long long
#define name "TASK"
using namespace std;
const int MAXN=1e5+5;
int n, m;
vector<int> adj[MAXN];
bool visited[MAXN];
void inp(){
cin>>n>>m;
for(int i=1;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 v:adj[u]){
if(!visited[v]){
dfs(v);
}
}
}
void connect(){
int cnt=0;
for(int i=1;i<=n;i++){
if(!visited[i]){
cnt++;
dfs(i);
}
}
cout<<cnt<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if (fopen(name ".INP", "r")) {
freopen(name ".INP", "r", stdin);
freopen(name ".OUT", "w", stdout);
}
inp();
connect();
return 0;
}
ngmanhduc29
Created at
2 likes