Solution of Matrix

O(n2*m2)

Putem considera matricea ca fiind un graf neorientat, cu noduri in patratele cu 1. Acum, daca construim cate un arbore dfs din fiecare nod al grafului, cel putin un ciclu ce contine nodul din care am pornit parcurgerea dfs va fi format din muchii de arbore si o singura muchie inversa (in cazul in care exista un astfel de ciclu). Se demonstreaza usor ca o muchie de intoarcere cu un capat in nodul de plecare este necesara si suficienta pentru un ciclu din nodul de placere. Aceasta solutie este ineficienta, neincadrandu-se in timp.

O(n*m)

Solutia buna se bazeaza pe solutia de mai sus. Problema este strans legata de determinarea punctelor de articulatie ale grafului. Pentru aceasta vom construi arborele dfs al grafului. Vom retine pentru fiecare nod h[i] - inaltimea nodului i din graf si o dinamica low[i] = cea mai mica inaltime la care se poate ajunge plecand din nodul i, mergand pe un lant in jos si apoi pe o muchie de intoarcere. Cu acestea cunoscute (relatia de recurenta este aceasi ca cea de la determinarea punctelor de articulatie), un nod i face parte din cel putin un ciclu daca si numai daca low[i]<=h[i] . Complexitatea toatala este astfel O(n*m), construind cate un astfel de arbore pentru fiecare componenta conexa a grafului.
    1 void dfs(int i,int j,int a,int b, int h) {
    2     viz[i][j]=1;
    3     depth[i][j]=low[i][j]=h;
    4     int ok=0;
    5     for(int d=0; d<4; ++d) {
    6         int ii=i+dx[d],jj=j+dy[d];
    7         if(!isIn(ii,jj) || mt[ii][jj]=='0') continue;
    8         if(ii==a && jj==b) continue;
    9         if(!viz[ii][jj]) {
   10             dfs(ii,jj,i,j,h+1);
   11             if(low[ii][jj]<=depth[i][j]) ok=1;
   12             low[i][j]=min(low[i][j],low[ii][jj]);
   13         }else {
   14             low[i][j]=min(low[i][j],depth[ii][jj]);
   15             if(depth[ii][jj]<=depth[i][j]) ok=1;
   16         }
   17     }
   18     rez+=ok;
   19 }
   20 
Questions?

Sponsors Gold