Một số bài tập chủ đề DFS và BFS

Bài 1: PolandBall and Forest

Nguồn: https://codeforces.com/problemset/problem/755/C

Tóm tắt: đếm số thành phần liên thông.

Code:

int n, cnt, vis[10005];                    
vector<int> adj[10005];
void dfs(int u) {
    vis[u] = 1;
    for(int v : adj[u]) {
        if(!vis[v]) dfs(v);
    }
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
    	int x; cin >> x;
    	adj[i].pb(x);
    	adj[x].pb(i);
    }
    for(int i = 1; i <= n; i++) {
    	if(!vis[i]) {
    	    ++cnt;
    	    dfs(i);
    	}
    }
    cout << cnt;
}

Bài 2: Two Buttons

Nguồn: https://codeforces.com/problemset/problem/520/B/

Tóm tắt: Có một thiết bị có 2 nút đỏ và xanh, nút đỏ sẽ nhân số lên 2 lần, nút xanh sẽ trừ số đi 1. Thao tác đến khi nào số âm thì dừng. Bắt đầu với số

$n$.

Nhận xét:

• Với

  $n>m$ thì với nút xanh ta luôn có cách để cho về
  $m$.

• Với

  $n<m$ thì với nút đỏ ta có thể nhân đôi số lên, nếu số
  $n$ khi đó lớn hơn
  $m$ thì ta vẫn có thể dùng nút xanh để giảm
  $n$ xuống.
  

• Giả sử ta có số

  $x$, thì số
  $x$ này có hai trạng thái là
  $2x$ (nút đỏ) và
  $x-1$ (nút xanh). Từ đó, ta có thể tạo đồ thị để
  $x$ nối với đỉnh
  $2x$ và
  $x$ nối với đỉnh
  $x-1$.

• Để biến

  $n$ thành
  $m$ ta phải thực hiện số lần ấn nút ít nhất hay tìm đường đi ngắn nhất từ
  $n$ đến
  $m$ bằng cách sử dụng duyệt BFS.

• Gọi

  $dp[i]$ là đường đi ngắn nhất từ
  $n$ đến
  $i$.

• Trường hợp cơ sở:

  $dp[n]=1$

• Mỗi lần thăm một đỉnh kề ta sẽ cập nhật trạng thái

  $dp[v]=dp[u]+1$ nghĩa là gán đường đi ngắn nhất mới bằng đường đi ngắn nhất cũ cộng thêm 1.

• Kết quả là

  $dp[m]-1$.

Code:

int n, m, dp[20005];
vector<int> adj[20005];                      
void bfs() {
    dp[n] = 1;
    queue<int> q;
    q.push(n);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v : adj[u]) {
            if(!dp[v]) {
                dp[v] = dp[u] + 1;
                q.push(v);
            }
        }
    }
}
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= 10000; i++) {
    	adj[i].pb(i - 1);
    	adj[i].pb(2 * i);
    }
    bfs();
    cout << dp[m] - 1;
}

Bài 3: Mr. Kitayuta's Colorful Graph

Nguồn: https://codeforces.com/problemset/problem/506/D

Tóm tắt: Cho một đồ thị có

$n$ đỉnh và

$m$ cạnh, mỗi đỉnh của đồ thị được đánh số từ

$1$ đến

$n$, cạnh thứ

$i$ có màu là

$c_i$ (

$1\le c_i\le m$) liên thông với đỉnh

$a_i$ và

$b_i$ (

$1\le a_i<b_i\le n$). Có

$q$ (

$1\le q\le {10}^5$) truy vấn, mỗi truy vấn cho hai số nguyên

$u_i$ và

$v_i$.

• Hãy tìm số màu thỏa mãn điều kiện: các cạnh của màu đó liên thông với đỉnh
  $u_i$ và đỉnh
  $v_i$ trực tiếp hoặc giản tiếp.

Sample input

4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4

Sample output

2
1
0

Giải thích:

• Đỉnh
  $1$ và đỉnh
  $2$ liên thông bởi màu đỏ và xanh dương.
• Đỉnh
  $3$ và đỉnh
  $4$ liên thông bởi màu xanh lá.
• Đỉnh
  $1$ và đỉnh
  $4$ không liên thông bởi màu nào cả.

Nhận xét:
Ta có thể tách đồ thị ra theo màu, nghĩa là có bao nhiêu màu thì tách ra bấy nhiêu đồ thị. Giả sử ta có màu

$c$ và đỉnh

$u$,

$v$ thì ta sẽ lưu ở mảng

$dp[c][u][v]$ (màu

$c$, đỉnh

$u$, đỉnh

$v$). Ta sẽ DFS trên đồ thị màu

$c$ đó và đánh dấu

$dp[c][u][v]=1$, với mỗi truy vấn chúng ta sẽ duyệt màu

$c$ nếu

$dp=1$ thì ta

$+1$ vào kết quả.

Code:

/* author : Tran Gia Huy */
#include <bits/stdc++.h>
using namespace std;
 
#define fast_paced ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define builtin_popcount __builtin_popcountll
#define fi first
#define se second
#define p64 pair<long long, long long>
#define p32 pair<int, int>
#define ll long long
#define ull unsigned long long
#define ldb long double
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define maxn 1000005

const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9;

// Might I solve this issue very expeditiously?
int n, m, dp[101][101][101];
bool vis[101];
void dfs(int i, int u) {
    vis[u] = true;
    for (int j = 1; j <= n; j++) {
        if (dp[i][u][j] && !vis[j]) dfs(i, j);
    }
}
void moon() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        dp[c][a][b] = dp[c][b][a] = 1;
    }
    int q; cin >> q;
    while (q--) {
        int u, v, ans = 0; cin >> u >> v;
        for (int i = 1; i <= m; i++) {
            memset(vis, false, sizeof vis);
            dfs(i, u);
            if (vis[v]) ++ans;
        }
        cout << ans << '\n';
    }
}
 
int main() {
    fast_paced
    int tt = 1; //cin >> tt;
    while(tt--) moon();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

/** -------------------- NOTES --------------------
	tách đồ thị ra từng màu khác nhau
	=> dp[color][dinh u][dinh v];
	dfs mỗi đỉnh u của màu c
    ----------------------------------------------- **/

Giải thích:

• Dòng 41: mỗi lần duyệt 1 đồ thị màu
  $c$ thì ta cần
  $memset$ mảng đánh dấu lại.
• Dòng 42: ta DFS từ đỉnh
  $u$ với mọi màu
  $i\le m$.
• Dòng 43: nếu đỉnh
  $v$ được thăm nghĩa là từ
  $u$ ta có thể đi đến
  $v$ với màu
  $c$ thì ta sẽ
  $+1$ kết quả.

Bài 4: Fillomino 2

Nguồn: https://codeforces.com/problemset/problem/1517/C

Tóm tắt: Cho một bàn cờ có kích thước

$n\ast n$. Các hàng được đánh số từ

$1$ đến

$n$ từ trên xuống dưới, các cột được đánh số từ

$1$ đến

$n$ từ trái sang phải. Một ô là giao của hàng thứ

$x$ và cột thứ

$y$ được ký hiệu là

$(x,y)$, đường chéo chính của bàn cờ là các ô

$(x,x)$ với

$(1\le x\le n)$. Với mỗi số trên đường chéo chính, chẳng hạn với số

$p$ thì hãy tìm cách xếp vào phía dưới đường chéo chính sao cho các dãy số

$p$ cùng thuộc một thành phần liên thông và xuất hiện đúng p lần (tính cả số ở đường chéo chính).

Ví dụ:

Với các số trên đường chéo chính đã nhập, ta có thể ra được đáp án như hình (số 2 xuất hiện 2 lần, số 3 xuất hiện 3 lần, số 1 xuất hiện 1 lần và với mỗi số đều thuộc một thành phần liên thông).

Ví dụ này tương tự.

Sample input 1:

3
2 3 1

Sample output 1:

2
2 3
3 3 1

Sample input 2:

5
1 2 3 4 5

Sample output 2:

1
2 2
3 3 3
4 4 4 4
5 5 5 5 5

Nhận xét:

• Với mỗi số ở đường chéo chính, ta sẽ ưu tiên điền nó vào hàng ngang trước cho đến khi nào không điền được nữa thì ta sẽ điền xuống dưới.

Code:

// author : Tran Gia Huy
#include "bits/stdc++.h"
using namespace std;
 
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define fi first
#define se second
#define p64 pair<long long, long long>
#define p32 pair<int, int>
#define ll long long
#define ull unsigned long long
#define ldb long double
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define maxn 1005

const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6;;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9;

int n, a[maxn][maxn], cnt;
void dfs(int u, int v, int x) {
    if (cnt > x) return;
    a[u][v] = x;
    if (v - 1 > 0 && a[u][v - 1] == 0) ++cnt, dfs(u, v - 1, x);
    if (u + 1 <= n && a[u + 1][v] == 0) ++cnt, dfs(u + 1, v, x);
}
void OnePunchAC() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	int x; cin >> x;
    	cnt = 1;
    	dfs(i, i, x);
    }
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= i; j++) {
            cout << a[i][j] << " \n"[j == i];
    	}
    }
}
 
int main() {
    fastIO
    int tt = 1; //cin >> tt;
    while(tt--) OnePunchAC();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

Bài 5: Lunar New Year and a Wander

Nguồn: https://codeforces.com/problemset/problem/1106/D

Tóm tắt: Công viên được biểu diễn dưới dạng đồ thị liên thông có

$n$ nút và

$m$ cạnh hai chiều. Ban đầu Bob đang ở nút

$1$ và anh ấy ghi lại

$1$ trên sổ ghi chép của anh ấy, anh ta có thể đi từ nút này sang nút khác và bất cứ khi nào anh ấy thăm một nút mà anh ấy chưa ghi chép lại thì anh ấy sẽ ghi chép lại nó. Hãy giúp Bob tìm chuỗi nút nhỏ nhất theo thứ tự từ điển mà anh ấy có thể ghi lại.

Sample input 1:

3 2
1 2
1 3

Sample output 1:

1 2 3 

Sample input 2:

5 5
1 4
3 4
5 4
3 2
1 5

Sample output 2:

1 4 3 2 5 

Sample input 3:

10 10
1 4
6 8
2 5
3 7
9 4
5 6
3 4
8 10
8 9
1 10

Sample output 3:

1 4 3 7 9 8 6 5 2 10

Nhận xét:

• Ta có thể sử dụng cấu trúc dữ liệu hàng đợi ưu tiên để giải quyết bài này.
• Với mỗi đỉnh kề với
  $u$ ta sẽ đi đến đỉnh nhỏ nhất.

Code:

// author : Tran Gia Huy
#include "bits/stdc++.h"
using namespace std;
 
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pf push_front
#define eb emplace_back
#define fi first
#define se second
#define p64 pair<long long, long long>
#define p32 pair<int, int>
#define ll long long
#define ull unsigned long long
#define ldb long double
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define maxn 100005

const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6;;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9;

int n, m, vis[maxn];
priority_queue<int> pq;
vector<int> a[maxn];
void OnePunchAC() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        a[x].eb(y);
        a[y].eb(x);
    }
    pq.push(-1);
    vis[1] = 1;
    while(!pq.empty()) {
        int u = -pq.top(); pq.pop();
        cout << u << " ";
        for (auto v : a[u]) {
            if(!vis[v]) {
                pq.push(-v);
                vis[v] = 1;
            }
    	}
    }
}
 
int main() {
    fastIO
    int tt = 1; //cin >> tt;
    while(tt--) OnePunchAC();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

Giải thích:

• Ở đây mình sẽ sử dụng một trick nhỏ là mình sẽ push số âm vào
  $pq$ sau đó lấy ra số đó nhưng mà gắn thêm dấu - trước nó thì sẽ ra được số nhỏ nhất.

Bài 6: Running for Gold

Nguồn: https://codeforces.com/problemset/problem/1552/B

Đề bài:
Đại hội thể thao Olympic vừa bắt đầu và Federico rất háo hức để xem cuộc đua marathon. Sẽ có

$n$ vận động viên, được đánh số từ

$1$ đến

$n$, cạnh tranh trong cuộc đua marathon và mỗi vận động viên trong quá khứ đều đã tham gia vào

$5$ cuộc thi marathon quan trọng, được đánh số từ

$1$ đến

$5$. Đối với mỗi

$1\le i\le n$ và

$1\le j\le 5$, Federico nhớ rằng vận động viên thứ

$i$ đạt hạng

$r_{i,j}$ trong cuộc thi marathon thứ

$j$ (ví dụ:

$r_{2,4}=3$ nghĩa là vận động viên thứ 2 đạt hạng 3 trong cuộc thi marathon thứ 4). Federico coi vận động viên

$x$ đạt hạng tốt hơn vận động viên

$y$ trong ít nhất

$3$ cuộc marathon trước đây, tức là

$r_{x,j}<r_{y,j}$ cho ít nhất

$3$ giá trị khác nhau của

$j$. Federico tin rằng một vận động viên có khả năng giành được huy chương vàng tại Olympic nếu anh ta vượt trội hơn các vận động viên còn lại.

Sample input 1:

4
1
50000 1 50000 50000 50000
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
6
9 5 3 7 1
7 4 1 6 8
5 6 7 3 2
6 7 8 8 6
4 2 2 4 5
8 3 6 9 4

Sample output 1:

1
-1
1
5

Nhận xét:
Vận động viên cuối cùng đạt hạng ít nhất ba lần là vận động viên thứ

$idx$. Để tính được

$idx$, ta sẽ kiểm tra từng vận động viên xem vận động viên

$i$ có hơn vận động viên

$i-1$ ít nhất ba giải hay không, nếu có cập nhật

$idx$ là vị trí của VĐV đó luôn.

Sau khi đã có

$idx$ thì ta tiếp tục duyệt lại. Nếu không có VĐV nào có từ ba giải trở lên thì thôi. Nếu có từ ba giải trở lên nghĩa là cùng bằng với VĐV

$idx$ mà ta tính được thì suy ra không dự đoán được VĐV nào.

Code:

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define setConstant memset

const int maxn = 1000005;

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt; cin >> tt;
	while (tt--) {
		int n; cin >> n;
		int a[n][5];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 5; j++) {
				cin >> a[i][j];
			}
		}

		/// Tim VDV hon VDV khac it nhat 3 giai
		int idx = 0;
		for (int i = 0; i < n; i++) {
			int tmp = 0;
			for (int j = 0; j < 5; j++) {
				if (a[i][j] < a[idx][j]) ++tmp;
			}
			if (tmp >= 3) idx = i;
		}
		bool ok = false;
		for (int i = 0; i < n; i++) {
			if (i == idx) continue;
			int tmp = 0;
			for (int j = 0; j < 5; j++) {
				if (a[i][j] > a[idx][j]) ++tmp;
			}
			if (tmp < 3) ok = true;
		}
		if (ok) cout << -1 << '\n';
		else cout << idx + 1 << '\n';
	}
	return 0;
}

Bài 7: Princesses and Princes

Nguồn: https://codeforces.com/contest/1327/problem/B

Đề bài:
Vua Polycarp LXXXIV có n con gái, được đánh số từ 1 đến n, và cũng có n vương quốc khác nhau. Mỗi công chúa đã lập danh sách các vương quốc mà cô muốn kết hôn. Quá trình kết hôn diễn ra theo cách tham lam, lần lượt cho từng công chúa. Đối với công chúa đầu tiên, Vua Polycarp chọn vương quốc có số thứ tự nhỏ nhất trong danh sách của cô và cho cô kết hôn với hoàng tử của vương quốc đó. Đối với công chúa thứ hai, ông chọn vương quốc có số thứ tự nhỏ nhất trong danh sách của cô, nhưng hoàng tử của vương quốc đó chưa được chọn trước đó. Nếu không có hoàng tử nào còn trống trong danh sách, công chúa không kết hôn và Vua Polycarp tiếp tục với công chúa tiếp theo. Quá trình này diễn ra cho đến công chúa thứ n.

Tuy nhiên, trước khi bắt đầu quá trình kết hôn, Vua Polycarp LXXXIV có thời gian thuyết phục một trong các công chúa của mình rằng có một hoàng tử khác cũng đáng kết hôn. Ông có thể thêm chính xác một vương quốc vào danh sách của một trong các công chúa. Lưu ý rằng vương quốc này không được có trong danh sách của công chúa đó.

Vua Polycarp LXXXIV muốn tăng số cặp kết hôn. Nếu không có cách nào để tăng số lượng cặp kết hôn, yêu cầu in ra "OPTIMAL". Nếu có nhiều cách để thêm một mục vào danh sách để tăng số lượng cặp kết hôn, in ra bất kỳ cách nào.

Đầu vào của bài toán bao gồm số lượng bộ test cases t, sau đó là t test cases. Mỗi test case bao gồm số nguyên n (1 ≤ n ≤ 10^5), số lượng công chúa và số lượng vương quốc. Tiếp theo là n dòng mô tả danh sách của mỗi công chúa. Dòng đầu tiên chứa số nguyên k (0 ≤ k ≤ n), là số lượng mục trong danh sách của công chúa thứ i. Sau đó là k số nguyên không trùng lặp g1, g2, …, gk (1 ≤ gi ≤ n), đại diện cho các vương quốc trong danh sách của công chúa thứ i.

Đầu ra của bài toán là kết quả cho từng test case. Nếu có thể thêm một vương quốc vào danh sách một công chúa để tăng số lượng cặp kết hôn, in ra "IMPROVE", sau đó in ra hai số nguyên là chỉ số của công chúa và chỉ số của vương quốc mà Vua Polycarp LXXXIV nên thêm vào danh sách của công chúa đó. Nếu có nhiều cách để thêm một mục vào danh sách để tăng số lượng cặp kết hôn, in ra bất kỳ cách nào. Nếu không có cách nào để thay đổi số lượng cặp kết hôn bằng cách thêm mục vào danh sách, in ra "OPTIMAL".

Sample input 1:

5
4
2 2 3
2 1 2
2 3 4
1 3
2
0
0
3
3 1 2 3
3 1 2 3
3 1 2 3
1
1 1
4
1 1
1 2
1 3
1 4

Sample output 1:

IMPROVE
4 4
IMPROVE
1 1
OPTIMAL
OPTIMAL
OPTIMAL

Nhận xét:
Ta duyệt qua từng con gái và từng hoàng tử trong danh sách. Nếu con gái và hoàng tử đang xét chưa được kết hôn với ai (biểu thức !a[i] && !b[j]), chương trình đánh dấu con gái và hoàng tử đó đã kết hôn bằng cách gán a[i] = b[j] = 1.

Tiếp theo, chương trình tìm vị trí đầu tiên của phần tử 0 trong mảng a (dòng int u = (find(all(a), 0ll) - a.begin())) và vị trí đầu tiên của phần tử 0 trong mảng b (dòng int v = (find(all(b), 0ll) - b.begin())). Nếu không tìm thấy phần tử 0 trong cả hai mảng, tức là không có cách nào để tăng số cặp kết hôn, chương trình in ra "OPTIMAL". Ngược lại, chương trình in ra "IMPROVE" cùng với vị trí của con gái và hoàng tử mà khi ghép cặp sẽ tạo ra một cặp kết hôn mới.

Code:

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define setConstant memset
#define int long long

const int maxn = 1000005;

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt; cin >> tt;
	while (tt--) {
		int n; cin >> n;
		vector<int> a(n), b(n);
		for (int i = 0; i < n; i++) {
			int k; cin >> k;
			while (k--) {
				int j; cin >> j; --j;
				if (!a[i] && !b[j]) {
					a[i] = b[j] = 1ll;
				}
			}
		}
		int u = (find(all(a), 0ll) - a.begin());
		int v = (find(all(b), 0ll) - b.begin());
		if (u == n) cout << "OPTIMAL" << '\n';
		else cout << "IMPROVE" << '\n' << u + 1 << " " << v + 1 << '\n';
	}
	return 0;
}

Bài 8: Network Topology

Nguồn: https://codeforces.com/problemset/problem/292/B

Đề bài:
Có ba loại mạng chính: mạng bus, mạng ring và mạng star.

Mạng bus là một mạng trong đó các máy tính được kết nối thông qua một đường cáp chung. Trong mạng bus, tất cả các nút đều kết nối với hai nút khác, trừ hai nút đầu và cuối của đường cáp.

Mạng ring là một mạng trong đó mỗi máy tính chỉ kết nối với hai máy tính khác. Các máy tính được kết nối thành một vòng.

Mạng star là một mạng trong đó có một nút trung tâm được kết nối với tất cả các nút khác trong mạng.

Đề bài yêu cầu người chơi xác định loại mạng của mạng đã cho. Nếu không thể xác định được, người chơi cần in ra "unknown topology" (loại mạng không xác định).

Đề bài cho biết đầu vào gồm hai số nguyên n và m, thể hiện số lượng nút và số lượng cạnh trong đồ thị mạng. Tiếp theo là m dòng mô tả các cạnh của đồ thị. Mỗi dòng chứa hai số nguyên xi và yi, thể hiện các nút được kết nối bởi một cạnh. Đồ thị được đảm bảo là liên thông. Có tối đa một cạnh nối hai nút bất kỳ với nhau.

Đầu ra của bài toán là in ra tên loại mạng của đồ thị đã cho. Nếu đồ thị tương ứng với mạng bus, in ra "bus topology". Nếu đồ thị tương ứng với mạng ring, in ra "ring topology". Nếu đồ thị tương ứng với mạng star, in ra "star topology". Nếu không có loại mạng nào phù hợp, in ra "unknown topology".

Sample input 1:

4 3
1 2
2 3
3 4

Sample output 1:

bus topology

Sample input 2:

4 4
1 2
2 3
3 4
4 1

Sample output 2:

ring topology

Sample input 3:

4 3
1 2
1 3
1 4

Sample output 3:

star topology

Sample input 3:

4 4
1 2
2 3
3 1
1 4

Sample output 3:

unknown topology

Nhận xét:
Khởi tạo mảng đếm số cạnh của đỉnh đồ thị.

Trường hợp bus topology:

Dựa vào hình trên, ta có thể thấy nếu ta đếm được đỉnh đầu và đỉnh cuối chỉ được nối với một và số lượng những đỉnh được nối bởi hai cạnh bằng với

$n-2$.

Trường hợp ring topology:

Dựa vào hình trên, ta có thể thấy mỗi đỉnh của đồ thị được nối bởi hai cạnh.

Trường hợp star topology:

Dựa vào hình trên, ta có thể thấy sẽ có đỉnh được nối nhiều hơn ba cạnh và tất cả các đỉnh còn lại thì chỉ nối với một cạnh.

Code:

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define setConstant memset

const int maxn = 1000005;

int adj[maxn];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		++adj[x]; ++ adj[y];
	}
	int a = 0, b = 0, c = 0;
	for (int i = 1; i <= n; i++) {
		if (adj[i] == 1) ++a;
		else if (adj[i] == 2) ++b;
		else ++c;
	}
	if (a == n - 1 && c != 0) cout << "star topology" << '\n';
	else if (b == n) cout << "ring topology" << '\n';
	else if (a == 2 && b == n - 2) cout << "bus topology" << '\n';
	else cout << "unknown topology" << '\n';

	return 0;
}