Advertisement
Mirbek

Компоненты связности

Jan 9th, 2022
1,139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 105;
  6.  
  7. int n;
  8. int used[N];
  9. int a[N][N];
  10.  
  11. void dfs(int v) {
  12.     used[v] = 1;
  13.     for (int i = 1; i <= n; i++) {
  14.         if (a[v][i] == 1 && used[i] == 0) {
  15.             dfs(i);
  16.         }
  17.     }
  18. }
  19.  
  20. int main(){
  21.     cin >> n;
  22.  
  23.     for (int i = 1; i <= n; i++) {
  24.         for (int j = 1; j <= n; j++) {
  25.             cin >> a[i][j];
  26.         }
  27.     }
  28.  
  29.     int cnt = 0;
  30.  
  31.     for (int i = 1; i <= n; i++) {
  32.         if (used[i] == 0) {
  33.             dfs(i);
  34.             cnt++;
  35.         }
  36.     }
  37.  
  38.     cout << cnt << endl;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement