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

#include<iostream>
#include<fstream>
using namespace std;
 
void xuat_mang(int arr[][100], int n);
int tim_bac_cua_dinh(int arr[][100], int n, int dinh);
int tim_so_canh(int arr[][100], int n);
int tim_dinh_co_lap(int arr[][100], int n);
 
 
int main()
{
	int n, dinh;
	int arr[100][100];
 
	// doc file
	ifstream file_in("socanh.inp",ios::in);
	file_in >> n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			file_in >> arr[i][j];
		}
	}
 
	return 0;
 
 
 
}
void xuat_mang(int arr[][100], int n)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cout<< arr[i][j]<<" ";
		}
		cout<<endl;
	}
}
 
int tim_bac_cua_dinh(int arr[][100], int n, int dinh)
{
	int bac=0;
	for(int j=0;j<n;j++)
	{
			bac+=arr[dinh-1][j];
	}
	return bac + arr[dinh-1][dinh-1];
}
int tim_so_canh(int arr[][100], int n)
{
	int so_canh=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			// tinh duong cheo tren 
			if(j>=i)
			{
				so_canh+=arr[i][j];
			}
		}
	}
	return so_canh;
}
void tim_dinh_co_lap(int arr[][100], int n)
{
	int dem=0;
	for(int i=0;i<n;i++)
	{
		int sum=0;
		for(int j=0;j<n;j++)
		{
			sum+=arr[i][j];	
		}
		if(sum == 0)
		{
			cout<<i+1<<" ";
			dem++;
		}
	}
	if(dem==0)
	{
		cout<<"Khong co dinh co lap!";
	}
}

Download Code