255
Cerința
Se dă un graf orientat cu n
noduri. Să se determine câte componente tare conexe are graful dat.
Date de intrare
Programul citește de la tastatură numărul n
de noduri și numărul m
de arce, iar apoi lista arcelor, formată din m
perechi de forma i j
, cu semnificația că există arc orientat de la nodul i
la nodul j
.
Date de ieșire
Programul va afișa pe ecran numărul C
de componente tare conexe.
Restricții și precizări
1 ≤ n ≤ 100
Exemplu
Intrare
5 7 1 2 2 1 2 4 4 1 3 5 4 5 5 3
Ieșire
2
Explicație
Cele două componente tare conexe sunt: 1 2 4
și 3 5
#include <bits/stdc++.h> using namespace std; vector <int> G[100002]; vector <int> H[100002]; int n , m , x , y , S[100001] , D[100001] , c; void dfs_succ(int v , int c) { S[v] = c; for(int i : G[v]) if(!S[i]) dfs_succ(i , c); } void dfs_pred(int v , int c) { D[v] = c; for(int i : H[v]) if(!D[i]) dfs_pred(i , c); } int main() { cin >> n >> m; for(int i = 1 ; i <= m ; i++) { cin >> x >> y; G[x].push_back(y); H[y].push_back(x); } for(int i = 1 ; i <= n ; i++) if(!S[i]) { c++; dfs_succ(i , c); dfs_pred(i , c); for(int i = 1 ; i <= n ; i++) if(S[i] != D[i]) S[i] = D[i] = 0; } cout << c; }
Comentarii