Advertisement
NamPNQ

Kiểm tra tính liên thông

Dec 11th, 2013
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. a = [
  2.         [0,1,1],
  3.         [1,0,1],
  4.         [1,1,0]
  5.     ];
  6. danhDau = [];
  7. soMienLienThong = 0;
  8. function xetLienThong () {
  9.     for (var i = 0; i < a.length; i++) { //Khoi tao chua duyet qua bat ki dinh nao
  10.         danhDau[i]=0;
  11.     };
  12.     soMienLienThong = 0;
  13.     for (var i = 0; i < a.length; i++) {
  14.         if(danhDau[i]===0) //Kiem tra chua duyet qua dinh hien tai
  15.         {
  16.             soMienLienThong ++;
  17.             thamDinh(i,soMienLienThong);
  18.         }
  19.     };
  20.     return soMienLienThong;
  21. }
  22. function thamDinh (i,mienLienThong) {
  23.     danhDau[i] = mienLienThong;
  24.     for (var j = 0; j < a.length; j++) {
  25.         if((danhDau[j]===0)&&(a[i][j]>0||a[j][i]>0)){//Duyet qua nhung dinh ke voi dinh dang xet
  26.             thamDinh(j,mienLienThong);//Tham dinh
  27.         }
  28.     };
  29.  
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement