树与图的深度优先遍历:
//用邻接表存储树图
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=100010;
bool st[N];
int h[N],e[N*2],ne[N*2],idx;//双向边范围要注意
int ans=N;//最终各个连通块中的点数的最大值
int n;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
st[u]=true;
int size=1;//当前这个大连通块点数的值
int res=0;//指的是割去某一个点后,剩余几个连通块的点数取最大值,max(size,n-size);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j);//j之后连接连通块的点数值
res=max(res,s);
size+=s;
}
}
res=max(res,n-size);
ans=min(ans,res);//最大连通块点数最小
return size;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);//初始化,一定要加
for(int i=0;i<n-1;i++)//输入n-1行的连接边的操作
{
//无向图双向边
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
广度优先遍历:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N];
int q[N];//队列
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
d[1]=0;
q[0]=1;//1入队
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(d[j]==-1)
{
d[j]=d[t]+1;
q[++tt]=j;//j入队
}
}
}
return d[n];
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);//不加必TLE
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
return 0;
}