Tìm đỉnh có bậc lớn nhất trên đồ thị vô hướng G

BÀI TOÁN
Viết chương trình tìm bậc cao nhất của đỉnh trong đồ thị với đồ thị vô hướng A[i,j] với A[i,j] = 1 nếu có đường đi từ i đến j và ngược lại A[i,j] = 0 nếu không có đường đi từ i đến j.
Dữ liệu vào: cho trong file Bai1.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng i+1 ( ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: thông báo kết quả ra màn hình số bậc cao nhất của đỉnh trong đồ thị đã cho.

Ví dụ:
6
0 1 1 0 0 0
1 0 0 1 1 0
1 0 0 0 1 0
0 1 0 0 1 0
0 1 1 1 0 1
0 0 0 0 1 0

Kết quả:BAC CAO NHAT : 4

HƯỚNG DẪN
Ý tưởng: tổng số phần tử khác không trên dòng i của ma trận liên kết chính là số bậc tương ứng của đỉnh i (i=1..n).
Trước tiên, ta gián bậc lớn nhất (BLN) của đỉnh bằng 0, tính bậc của từng đỉnh bằng cách đếm các chỉ số khác không của ma trận liên kết theo dòng và so sánh với bậc lớn nhất. Nếu bậc của đỉnh tương ứng lớn hơn BLN ta gián BLN bằng bậc của đỉnh tương ứng. Thuật toán kết thúc khi ta đã duyệt qua tất cả các đỉnh của đồ thị.

CHƯƠNG TRÌNH MẪU

Code:

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define TenFile "Bai1.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int **A,int &n) {
  FILE*f = fopen(TenFile,"rb");      //Mở file dữ liệu
  fscanf(f,"%d",&n);            //Đọc số đỉnh của đồ thị
  *A = new int [n];      //Cấp phát số vùng nhớ tương ứng theo chiều ngang
  cout<<"Ma Tran Lien Ket Cua Do Thi";
  for(int i =0;i<n;i++) {
      A[i] = new int [n];        //Cấp phát vung nhớ theo chiều rộng
      cout<<endl;
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<"  "<<A[i][j];
      }
  }
  fclose(f);              //Đóng file dữ liệu
}
/*Hàm trả về bậc lớn nhất của đỉnh*/
int BacLonNhat(int**A,int n) {
  int max = 0,Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)        //Tính bậc của từng đỉnh
        Bac++;
      if(Bac > max)    max = Bac;
  }
  return max;            //Trả về bậc lớn nhất 
}
/*Chương trình chính*/
void main() {
  clrscr();
  int **A,n;
  Doc_File(A,n);
  cout<<"\n1. Bac Lon Nhat Cua Dinh: "<<BacLonNhat(A,n);
  delete*A;
  getch();
}
Xử lý mở rộng:
/*Hàm trả về bậc nhỏ nhất của đỉnh*/
int BacNhoNhat(int**A,int n){
  int min = MAXINT,Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac < min)
        min = Bac;
  }
  return min;
}
/*Hàm trả về tổng bậc của đồ thị*/
int TongBac(int**A,int n){
  int Tong = 0;
  for(int i = 0; i<n; i++)
  for(int j = 0; j<n; j++)
  if(A[i][j]>0)
      Tong++;
  return Tong;
}
/*Thủ tục liệt kê các đỉnh có bậc nhỏ nhất*/
void DinhBacNhoNhat(int**A, int n){
  int min = BacNhoNhat(A,n), Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac == min)
        cout<<"  "<<i+1;
  }
}
/*Thủ tục liệt kê các đỉnh có bậc lớn nhất*/
void DinhBacLonNhat(int**A, int n){
  int max = BacLonNhat(A,n), Bac;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac == max)
        cout<<"  "<<i+1;
  }
}
/*Thủ tục liệt kê các đỉnh bậc chẵn và số đỉnh bậc chẵn*/
void DinhBacChan(int**A, int n) {
  int Bac,Tong=0;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac%2==0) {
        cout<<"  "<<i+1;
        Tong++;
      }
  }
  cout<<"\n\t So Dinh Bac Chan: "<<Tong;
}
/*Thủ tục liêt kê các đỉnh bậc lẻ và số đỉnh bậc lẻ*/
void DinhBacLe(int**A, int n){
  int Bac,Tong=0;
  for(int i = 0; i<n; i++) {
      Bac = 0;
      for(int j = 0; j<n; j++)
      if(A[i][j]>0)
        Bac++;
      if(Bac%2==1) {
        cout<<"  "<<i+1;
        Tong++;
      }
  }
  cout<<"\n\t So Dinh Bac Le: "<<Tong;
}