Bella: /* Componente tare conexe */

2019-11-27T14:23:35Z

Componente tare conexe

New page

== Tare conexitate ==
Definiții: Fie G=(V,U) un graf orientat.

Graful se numește conex dacă între oricare două noduri distincte există cel puțin un lanț.

Se numește componentă conexă un subgraf conex și maximal cu această calitate – dacă am mai adauga un nod, n-ar mai fi conex.

Graful se numește ''''tare conex'''' dacă pentru orice pereche de noduri distincte (x,y) există cel puțin un drum de la x la y și există cel puțin un drum de la y la x.

Se numește componentă '''tare conexă''' un subgraf tare conex și maximal cu această calitate – dacă am mai adauga un nod, n-ar mai fi tare conex.

=== [https://www.pbinfo.ro/?pagina=probleme&id=583 Componente tare conexe] ===
Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.
<syntaxhighlight>
/*
multimea elementelor componentei conexe din care face parte un nod i, este intersectia dintre
multimea succesorilor ( nodurile la care pot sa ajung pornind din i )
si mutimea predecesorilor nodului i( nodurile din care pot ajunge la i)

Cum detemrinam cele doua mutimi?
Multimea Succesorilor o determin parcurgand graful cu DFS de la nodul i.
Vom marca succesorii in vectorul s cu i ( daca un nod x e succesor al lui i atunci s[x] = i

Multimimea Predecesorilor o vom afla tot parcurgand cu DFS din nodul i, doar ca voi lua sensul invers al arcelor

*/

#include <iostream>
#include <fstream>
using namespace std;

int a[105][105], n;
int suc[105];
int pred[105];
int start; // nodul din care pornesc dfs
int nrcomp;
void df1( int nod ){
suc[nod] = nrcomp; // marchez nodurile cu nr nodului din care am pornit dfs
for( int i = 1; i <= n; i ++ ) // parcurg toti vecinii
if( suc[i] == 0 && a[nod][i] == 1 ) // daca nu a fost vizitat ( nu l-am marcat in vectorul de succesori )
df1( i ); // pornesc parcurgerea din acest nod
}

void df2( int nod ){
pred[nod] = nrcomp;
for( int i = 1 ; i <= n ; i ++ )
if( pred[i] == 0 && a[i][nod] == 1 )
df2( i );
}

int main(){
int i, j, x, y, m;
cin >> n >> m;
for( i = 1; i <= m; i++ ){
cin >> x >> y;
a[x][y] = 1;
}
nrcomp = 0; // nr comp tare conexe gasite
for( start = 1; start <= n; start++ ) // luam pe rand toate nodurile grafului
if( suc[start] == 0 ){ // daca nodul nu face parte dintr-o comp tare conexa
nrcomp ++; // am mai gasit o componenta tare conexa
suc[start] = nrcomp; // marcam in vectorul succesor pentru nodul stard nr componentei conexe din care face parte
df1(start); df2(start); // parcurgem graful in adancime, determinand succesorii si predecesorii nodului start
for(int j = 1; j <= n ; j ++ ) // verificam toate nodurile grafului
if(suc[j] != pred[j] ) // daca suc[i]!=pred[j] nodul j nu face parte din comp conexa curenta
suc[j] = pred[j] = 0;
}
cout << nrcomp << "\n";
return 0;
}
</syntaxhighlight>
== Articole ==
Infoarena: https://www.infoarena.ro/problema/ctc
= Tema =
*[https://www.infoarena.ro/problema/plan plan]

Clasa a XI-a lecția 23 - Revision history

Bella: /* Componente tare conexe */