Advertisement
fooker

number of connected components (using dfs/adjacency matrix)

Nov 21st, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. const int MN=1e5+10;
  5. bool visited[MN];
  6. vector<int> adj_list[MN];
  7. void dfs(int x){
  8.     visited[x]=true;
  9.     for (int u:adj_list[x]){
  10.         if (!visited[u]){
  11.             dfs(u);
  12.         }
  13.     }
  14. }
  15. int connected_components(){
  16.     int counter=0;
  17.     for (int i=1; i<=n; i++){
  18.         if (!visited[i]){
  19.             counter++;
  20.             dfs(i);
  21.         }
  22.     }
  23.     return counter;
  24. }
  25. int main()
  26. {
  27.     int t;
  28.     cin>>t;
  29.     while(t--){
  30.         cin>>n;
  31.         int a[100][100];
  32.         for (int i=1; i<=n; i++){
  33.             for (int j=1; j<=n; j++){
  34.                 cin>>a[i][j];
  35.                 if (a[i][j]==1){
  36.                     adj_list[i].push_back(j);
  37.                 }
  38.             }
  39.         }
  40.         cout<<connected_components<<"\n";
  41.     }
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement