6. heti jegyzet (2014.11.13.)

Órai anyag:

Elvágó pontok megkeresése összefüggő irányítatlan gráfban:
main
| t:=0
| for i:=0 to n-1
| | ep[i]:=volt[i]:=false
| mély(0)
| gygy:=0 //gyökér gyerekszáma
| for i:=1 to n-1
| | if me[i]>=elérés[hon[i]]
| | | ep[hon[i]]:=true //elvágó pont
| | if hon[i]==0
| | | gygy++;
| ep[0]:=gygy>1;
mély(x)
| me[x]:=elérés[x]:=t++
| volt[x]:=true
| foreach y in szomszédok(x)
| | if !volt[y]
| | | hon[y]:=x
| | | mely(y)
| | | if me[x]>me[y]
| | | | me[x]=me[y]
| | else
| | | if y!=hon[x] && me[x]>elérés[y]
| | | | me[x]=elérés[y]

Erősen összefüggő komponensek megkeresése.


Házi:

Keressük meg az elvágó pontokat nem-összefüggő irányítatlan gráfban!