#include<iostream>
using namespace std;
int N = 1e5 + 10,M = N*2;
//h表示鏈表頭,e存儲的是所有的邊,ne表示所有的next指針是多少,相當與n個單鏈表
int h[N],e[M],ne[M],idx;
//深度優先搜索和寬度優先搜索每個點只會遍歷一次
bool st[N];//存一下那些點已經被遍歷過了,就不要再遍歷他了
void add(int a,int b){//a前插入b
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//樹和圖的深度優先搜索的代碼 時間復雜度是O(n + m),因為點數和邊數呈線性關系
//u表示已經遍歷到這個節點了
int dfs(int u){
st[u] = true;//首先先標記下當前這個點已經被搜索過了
//遍歷下u的所有的初邊
for(int i = h[u];i != -1;i = ne[i]){
// 存儲當前結點對應圖里邊結點的編號是多少
int j = e[i];
//如果當前點沒有做過的話,就一直搜,一條路走到黑
if(!st[j]) dfs(j);
}
}
int main(){
//頭結點指向-1,n給單鏈表的頭結點指向-1
memset(h,-1,sizeof h);
dfs(1);//從第一個點開始搜索
}
例題:
846. 樹的重心
給定一顆樹,樹中包含n個結點(編號1~n)和n-1條無向邊。
請你找到樹的重心,并輸出將重心刪除后,剩余各個連通塊中點數的最大值。
重心定義:重心是指樹中的一個結點,如果將這個點刪除后,剩余各個連通塊中點數的最大值最小,那么這個節點被稱為樹的重心。
輸入格式
第一行包含整數n,表示樹的結點數。
接下來n-1行,每行包含兩個整數a和b,表示點a和點b之間存在一條邊。
輸出格式
輸出一個整數m,表示重心的所有的子樹中最大的子樹的結點數目。
數據范圍
1≤n≤1051≤n≤105
輸入樣例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
輸出樣例:
4
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10,M = N*2;
//h表示鏈表頭,e存儲的是所有的邊,ne表示所有的next指針是多少,相當與n個單鏈表
int h[N],e[M],ne[M],idx,n;
int ans = N;//全局的答案存儲最小的最大值
//深度優先搜索和寬度優先搜索每個點只會遍歷一次
bool st[N];//存一下那些點已經被遍歷過了,就不要再遍歷他了
void add(int a,int b){//a前插入b
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//樹和圖的深度優先搜索的代碼 時間復雜度是O(n + m),因為點數和邊數呈線性關系
//u表示已經遍歷到這個節點了
//以u為根的子樹中點的數量
int dfs(int u){
st[u] = true;//首先先標記下當前這個點已經被搜索過了
//記錄當前子樹的大小
int sum = 1;
int res = 0;//表示當前連通塊的最小值的最大值
//遍歷下u的所有的初邊
for(int i = h[u];i != -1;i = ne[i]){
// 存儲當前結點對應圖里邊結點的編號是多少
int j = e[i];
//如果當前點沒有做過的話,就一直搜,一條路走到黑
if(!st[j]) {
//表示當前子樹的大小
int s = dfs(j);
//當前的子樹也算是一個連通塊
res = max(res,s);
//當前子樹也是我們的子樹的一部分
//s為根的子樹是以u為根節點的子樹的一部分
sum += s;
}
}
res = max(res,n - sum);
// cout << u << " " << sum;
//最后res存的就是刪除當前這個點之后所存儲的最大的點數了
ans = min(res,ans);
return sum;
}
int main(){
//頭結點指向-1,n給單鏈表的頭結點指向-1
memset(h,-1,sizeof h);
cin >> n;
for(int i = 0;i < n - 1;i++){
int a,b;
cin >> a >> b;
add(a,b),add(b,a);
}
dfs(1);//從第一個點開始搜索
cout << ans;
}
浙公網安備 33010602011771號