fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int MAXN=500005;
  6.  
  7. vector<int> adj[MAXN];
  8. int col[MAXN];
  9.  
  10. void dfs(int v, int b){
  11. col[v]=b;
  12. for(int u: adj[v]){
  13. if(col[u]==0)
  14. dfs(u, b);
  15. }
  16. }
  17.  
  18.  
  19.  
  20.  
  21.  
  22. int main() {
  23. ios_base::sync_with_stdio(false);
  24. cin.tie(NULL);
  25. int n,m;
  26. cin>>n>>m;
  27. for(int i=0; i<m; i++){
  28. int a,b;
  29. cin>>a>>b;
  30. adj[a].push_back(b);
  31. adj[b].push_back(a);
  32. }
  33. int ile=0;
  34. for(int i=1; i<n+1; i++){
  35. if(col[i]==0){
  36. ile++;
  37. dfs(i, ile);
  38. }
  39. }
  40.  
  41. cout<<ile;
  42.  
  43. return 0;
  44. }
Success #stdin #stdout 0.01s 15960KB
stdin
6 4
3  6
2 3
4 6
4 2
stdout
3