Advertisement
Saleh127

Spoj Prayatna PR

Oct 23rd, 2020
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. vector<ll>graph[100005];
  6. bool visit[100005];
  7.  
  8. void dfs(ll x)
  9. {
  10. visit[x]=1;
  11. for(ll i=0;i<graph[x].size();i++)
  12. {
  13. ll nx=graph[x][i];
  14. if(visit[nx]==0)
  15. {
  16. dfs(nx);
  17. }
  18. }
  19. }
  20.  
  21. int main()
  22. {
  23. ios_base::sync_with_stdio(0);
  24. cin.tie(0);cout.tie(0);
  25.  
  26. test
  27. {
  28.  
  29. memset(visit,0,sizeof(visit));
  30. memset(graph,0,sizeof(graph));
  31.  
  32. ll n,m,a,c,d,e,i,j,k,l=0;
  33.  
  34. cin>>n>>m;
  35. for(i=0;i<m;i++)
  36. {
  37. cin>>a>>c;
  38. graph[a].push_back(c);
  39. graph[c].push_back(a);
  40. }
  41.  
  42. for(i=0;i<n;i++)
  43. {
  44. if(visit[i]==0)
  45. {
  46. l++;
  47. dfs(i);
  48. }
  49. }
  50. cout<<l<<endl;
  51. }
  52.  
  53. return 0;
  54. }
  55.  
Advertisement
RAW Paste Data Copied
Advertisement