青大孙浩宇今日份4.3学习日记（深搜遍历树，广搜遍历树，拓扑排序）

1、树的深搜（邻接表）

树的重心
https://www.acwing.com/problem/content/848/
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小	，那么这个节点被称为树的重心。

输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4

分析：1、他题目中说了是无向图，可以看成特殊的有向图
          2、进行图的深搜有一个模板
          3、具体看代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],e[N*2],ne[N*2],idx,n;//注意这个地方的e是要开两倍的N的规模的因为是双向图，建立两条边
bool st[N];
int ans = 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 sum = 1,res = 0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            sum += s;
            res = max(s,res);
        }
    }
    res = max(res,n-sum);
    ans = min(ans,res);
    return sum;
}
int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        add(l,r);
        add(r,l);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

2、树的宽搜（也是邻接表）用数组模拟的话比STL快一些

图中点的层次
https://www.acwing.com/problem/content/849/
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4

1、注意这是一个有向图
2、用数组模拟队列的话要设置几个变量：hh队首，tt队尾，d[i]表示i节点的深度
3、具体看代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],e[N*2],ne[N*2],idx,n;
bool st[N];
int ans = 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 sum = 1,res = 0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j]){
            int s = dfs(j);
            sum += s;
            res = max(s,res);
        }
    }
    res = max(res,n-sum);
    ans = min(ans,res);
    return sum;
}
int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        add(l,r);
        add(r,l);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

3、有向图的拓扑排列

https://www.acwing.com/problem/content/850/
分析：类似于偏序关系，到一个点的所有点的数量叫做一个点的入度，出去的所有点的数量叫做一个点的出度
题目：

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围
1≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

1、注意拓扑队列是一个有向图
2、对每一次入度为0的节点入队
3、遍历队列中的每一个点，然后他的子节点入度都减一，因为这个点已经出队了
4、如果最后在队列里的元素不满n个则返回不存在
5、具体看代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010,M = 2*N;
int h[N],q[N],d[N],e[N],ne[N],idx,n,m;//d数组记录的是每个点的入度
bool st[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool bfs(){
    int hh = 0,tt = -1;
    for(int i=1;i<=n;i++) if(!d[i]) q[++tt] = i;
    while(hh <= tt){
        int t = q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n-1;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    if(!bfs()) cout<<"-1";
    else{
        for(int i=0;i<n;i++) cout<<q[i]<<" ";
        cout<<endl;
    }
    return 0;
}