Header Ads Widget

Ticker

6/recent/ticker-posts

Tìm bậc của đỉnh, số cạnh, đỉnh cô lập trong ma trận kề



 Bài 1. Cho trước đồ thị vô hướng G = (V, E) cấp N (số nguyên dương) và một đỉnh v ∈
V. Hãy viết chương trình tìm bậc của đỉnh v.
Input:
- Tên file: bacdinh.inp.
- Trong file này, dòng đầu tiên là số N, N dòng tiếp theo là ma trận kề cấp N.
- Dòng sau ma trận là đỉnh v.
Output: in kết quả ra màn hình và ra file “bacdinh.out”.
Bài 2. Cho trước đồ thị vô hướng G = (V, E) cấp N (số nguyên dương). Hãy viết
chương trình tìm số cạnh của đồ thị G.
Input:
- Tên file: socanh.inp.
- Trong file này, dòng đầu tiên là số N, N dòng tiếp theo là ma trận kề cấp N.
Output: in kết quả ra màn hình và ra file socanh.out.
Bài 3. Cho trước đồ thị vô hướng G = (V, E) cấp N (số nguyên dương). Hãy viết
chương trình kiểm tra xem trong đồ thị G có định cô lập hay không, nếu có thì cho biết
tên đỉnh đó.
Input:
- Tên file: dinhcl.inp.
- Trong file này, dòng đầu tiên là số N, N dòng tiếp theo là ma trận kề cấp N.
Output: in kết quả ra màn hình và ra file dinhcl.out




  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4.  
  5. void xuat_mang(int arr[][100], int n);
  6. int tim_bac_cua_dinh(int arr[][100], int n, int dinh);
  7. int tim_so_canh(int arr[][100], int n);
  8. int tim_dinh_co_lap(int arr[][100], int n);
  9.  
  10.  
  11. int main()
  12. {
  13. int n, dinh;
  14. int arr[100][100];
  15.  
  16. // doc file
  17. ifstream file_in("socanh.inp",ios::in);
  18. file_in >> n;
  19. for(int i=0;i<n;i++)
  20. {
  21. for(int j=0;j<n;j++)
  22. {
  23. file_in >> arr[i][j];
  24. }
  25. }
  26.  
  27. return 0;
  28.  
  29.  
  30.  
  31. }
  32. void xuat_mang(int arr[][100], int n)
  33. {
  34. for(int i=0;i<n;i++)
  35. {
  36. for(int j=0;j<n;j++)
  37. {
  38. cout<< arr[i][j]<<" ";
  39. }
  40. cout<<endl;
  41. }
  42. }
  43.  
  44. int tim_bac_cua_dinh(int arr[][100], int n, int dinh)
  45. {
  46. int bac=0;
  47. for(int j=0;j<n;j++)
  48. {
  49. bac+=arr[dinh-1][j];
  50. }
  51. return bac + arr[dinh-1][dinh-1];
  52. }
  53. int tim_so_canh(int arr[][100], int n)
  54. {
  55. int so_canh=0;
  56. for(int i=0;i<n;i++)
  57. {
  58. for(int j=0;j<n;j++)
  59. {
  60. // tinh duong cheo tren
  61. if(j>=i)
  62. {
  63. so_canh+=arr[i][j];
  64. }
  65. }
  66. }
  67. return so_canh;
  68. }
  69. void tim_dinh_co_lap(int arr[][100], int n)
  70. {
  71. int dem=0;
  72. for(int i=0;i<n;i++)
  73. {
  74. int sum=0;
  75. for(int j=0;j<n;j++)
  76. {
  77. sum+=arr[i][j];
  78. }
  79. if(sum == 0)
  80. {
  81. cout<<i+1<<" ";
  82. dem++;
  83. }
  84. }
  85. if(dem==0)
  86. {
  87. cout<<"Khong co dinh co lap!";
  88. }
  89. }
Download Code

Đăng nhận xét