Clasa a XI-a lecția 23

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.

Componente tare conexe

Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.

/*
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;
}

Articole

Infoarena: https://www.infoarena.ro/problema/ctc

Tema

• plan