fork(2) download
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. int n, m; // орой болон ирмэгийн тоо
  6. int comp; // бидний хариу буюу компонентийн тоо
  7. bool vis[200000]; // ирсэн ирээгүйг хадгалах массив
  8. vector<int> adj[200000]; // графын мэдээллийг хадгалах вектор
  9.  
  10. void dfs(int u) {
  11. // одоо бид u гэсэн орой дээр ирж байгаа тул
  12. vis[u] = 1; // ирсэн гэж тэмдэглэнэ
  13.  
  14. for(int v:adj[u]) {
  15. // v:adj[u] гэдэг нь v гэсэн тоо нь adj[u] гэсэн векторт байгаа
  16. // бүх элемэнтийн утгыг авна гэсэн үг ба эхнээс нь дуустал явна
  17. if( !vis[v] ) {
  18. // v гэсэн орой дээр өмнө нь ямар нэгэн байдлаар очоогүй бол
  19. // энэ оройгоос цааш явах ёстой гэсэн үг
  20. dfs(v);
  21. }
  22. }
  23. }
  24.  
  25. int main() {
  26. cin >> n >> m;
  27. while( m-- ) {
  28. int u, v; // u, v 2 орой хоорондоо шууд ирмэгээр
  29. // холбогддог гэсэн үг
  30. cin >> u >> v;
  31. adj[u].push_back( v );
  32. adj[v].push_back( u );
  33. }
  34.  
  35. for(int i = 1; i <= n; i++) {
  36. if( !vis[i] ) {
  37. // Энэ нь I-р орой дээр өмнө ямар нэгэн байдлаар очиж чадаагүй
  38. // гэсэн үг тул энэ оройг агуулсан нэг компонент байх нь
  39. // тодохрой тул компонентын тоо нь 1-р нэмэгдэнэ
  40. comp++;
  41. dfs( i ); // энэ оройтой ямар нэгэн байдлаар холбогдсон бүх
  42. // орой нь энэ компонетэд орно.
  43.  
  44. }
  45. }
  46. cout << comp << endl; // хариуг хэвлэнэ.
  47. return 0;
  48. }
Success #stdin #stdout 0s 20120KB
stdin
5 4
1 2
2 3
1 3
4 5
stdout
2