Guest User

Untitled

a guest
May 24th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.63 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <queue>
  6.  
  7. using namespace std;
  8. vector<int> a[1001];
  9. bool check[1001];
  10.  
  11. void dfs(int node) {
  12. check[node] = true;
  13. for (int i = 0; i<a[node].size(); i++) {
  14. int next = a[node][i];
  15. if (check[next] == false) {
  16. dfs(next);
  17. }
  18. }
  19. }
  20.  
  21. int main() {
  22. int n, m;
  23. scanf("%d %d", &n, &m);
  24. for (int i = 0; i<m; i++) {
  25. int u, v;
  26. scanf("%d %d", &u, &v);
  27. a[u].push_back(v);
  28. a[v].push_back(u);
  29. }
  30. int components = 0;
  31. for (int i = 1; i <= n; i++) {
  32. if (check[i] == false) {
  33. dfs(i);
  34. components += 1;
  35. }
  36. }
  37. printf("%d\n", components);
  38.  
  39. return 0;
  40. }
Add Comment
Please, Sign In to add comment