e943 - pD. 最大群問題
題目描述
題目要求找出一個圖中，互相連接（朋友關係）的最大節點數量，也就是最大朋友群的人數。給定 N 個人和 M 組朋友關係，輸出最大朋友群的大小。
解題思路
這題可以使用深度優先搜尋 (DFS) 或回溯法來解決。基本思路是枚舉所有可能的子集，然後檢查每個子集是否是一個朋友群。如果一個子集中的所有人都互相是朋友，那麼這個子集就是一個朋友群。我們需要找到大小最大的朋友群。
程式碼中，dfs 函數遞迴地尋找朋友群。used 陣列儲存目前找到的朋友群中的成員。對於每個節點，我們檢查它是否可以加入目前的朋友群，如果可以，就將它加入 used 陣列，並遞迴地尋找更大的朋友群。w 陣列表示朋友關係，w[i][j] = 1 表示 i 和 j 是朋友。
複雜度分析
- 時間複雜度: O(2^N) 因為最壞情況下需要遍歷所有可能的子集。
- 空間複雜度: O(N) 主要用於儲存
used陣列和w陣列。
程式碼
#include <iostream>
using namespace std;
int n,m,k,w[25][25],ans,x,y,used[25];
void dfs(int it,int v){
if(ans<v){
ans=v;
/*for(int i=0;i<v;++i){
cout << used[i] << " ";
}
cout << "\n";*/
}
for(int i=it+1;i<=n;++i){
int ac=1;
for(int j=0;j<v&∾++j){
if(w[i][used[j]]==0)ac=0;
}
if(ac){
used[v]=i;
dfs(i,v+1);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<=n;++i){
w[i][i]=1;
}
for(int i=0;i<m;++i){
cin >> x >> y;
w[x][y]=w[y][x]=1;
}
for(int i=1;i<=n;++i){
used[0]=i;
dfs(i,1);
}
cout << ans;
}