拓扑排序和LCA

· · 个人记录

小黑板

首先我们先来了解一下什么事最近公共祖先，最近公共祖先就是两个点的第一个同一个的祖先，我们称作最近公共祖先。

那么我们的 LCA 就是专门求最近公共祖先的，那么我们就来看看这几种求最近公共祖先的方法吧。

LCA

① 染色法

首先我们知道最近公共祖先一定是一个人的父亲的父亲的……，然后最近的公共祖先一定就是另一个人的祖先中和这个人祖先是一样的祖先。

那么我们是不是可以这样想呢？首先我们找到一个人的所有祖先，然后找到另一个人的所有祖先之后再找到公共且最近的。

那一个人的公共祖先我们就可以全部标记，然后我们再找另一个人的祖先当找到被标记的点时，那么这个点不就是最近公共祖先吗？

② 上走法

上走法其实十分的好理解。首先我们可以知道一个人的父亲的深度是不是比自己小，然后祖先不就是一直向上走吗。

然后最近的公共祖先不就是这两个点一直向上走只不过走直到走到最近公共祖先。只不过走到步数不相同而已。

那么我们就根据这个想法让这两个点一直向上走，但是我们要求的是最近公共祖先所以要保持一致的深度，不然你一上一下上的都略过最近公共祖先了。

拓扑排序

解决了 LCA 我们就要开始进入新的知识拓扑排序了。首先我问你一些问题。

假设你要学会英语口语，你就要学会英语绘本。

假设你要学会英语绘本，你就要学会英语单词。

假设你要学会英语单词，你就要学会英语字母。

那么我们知道想要解决了事情 A 你要先解决事情 B 而想要解决事情 B 又要解决其他的，这种其实就是一个拓扑了。

那么我们遇到这样的问题要怎么解决呢？拿上面的例子我们知道你要完成 A 要解决 B 那么不就是 B 指向了 A 吗。

那么我们解决这种问题不就是把所有入度为0的全部取出来慢慢的解决这些问题，在利用这些问题解决其他的问题吗？

P3379 【模板】最近公共祖先（LCA）

遇到这道题首先我们要知道一些事，那就是题目并没有给出谁是谁的儿子那么当你建边时你就不能建单项变，要建双向边。

然后因为你只知道根节点不知道谁是谁的儿子，所以你就要在统计深度的时候就要顺便统计一下谁是谁的儿子。

那么我为了凑个字数就讲一讲如何求解深度吧。首先求解深度我们知道一个事情，那就是自己的深度必定是父亲深度加上 1 得来的。

那么我们就可以根据这个尿性没往下搜一次深度就是父亲节点的深度加 1 就是这个节点的深度了，这样我们就可以求出所有点的深度了

code

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
vector<int>E[500005];
int dep[500005],fa[500005];
void dfs(int u,int f){
    dep[u] = dep[f] + 1;
    fa[u] = f;
    for(int i = 0 ; i < E[u].size() ; i ++){
        int v = E[u][i];
        if(v != f){
            dfs(v , u);
        }
    }
}
int lca(int x,int y){
    while(x != y){
        if(dep[x] >= dep[y]){
            x = fa[x];
        }else{
            y = fa[y];
        }
    }
    return x;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1 ; i < n ; i ++){
        int x,y;
        cin >> x >> y;
        E[y].push_back(x);
        E[x].push_back(y);
    }
    dfs(s , s);
    while(m --){
        int x,y;
        cin >> x >> y;
        cout << lca(x , y) << "\n";
    }
    return 0;
}

P2712 摄像头

本题目其实跟我讲的那个例子十分向像你拆掉这个摄像头的话就必须删掉另一个摄像头那么我们就可以首先把所有入度为0的放入一个队列中

然后我们就可以把我们送进来的点全部给删除，当然不是真正的删除，我们要把这个点指向的边的入度减1，代表着指向的这个点的点少了一个。

然后我们还要注意，当我们把某个点删除后，这个点指向的某一个点已经没有点指向它了，那么我们又可以把这个点删了。这个点就要入队。

最后我们要统计一下删了多少个点，如果所有摄像头都被拆除了那么我们就要输出 YES 了，否则我们就要输出还剩几个摄像头

code

#include<bits/stdc++.h>
using namespace std;
int n,sum;
int in[505],a[105];
bool vis[505],f[505];
vector<int>E[505];
void bfs(){
    queue<int> q;
    for(int i = 1 ; i <= n ; i ++){
        if(in[a[i]] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(!vis[u]){
            vis[u] = 1;
            sum ++;
            for(int i = 0 ; i < E[u].size() ; i ++){
                int v = E[u][i];
                in[v] --;
                if(in[v] == 0){
                    q.push(v);
                }
            }
        }
    }
    if(sum == n){
        cout << "YES";
    }else{
        cout << n - sum;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0); 
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        int T;
        cin >> a[i] >> T;
        f[a[i]] = 1;
        while(T --){
            int x;
            cin >> x;
            E[a[i]].push_back(x);
            in[x]++;
        }
    }
    bfs();
    return 0;
}

D1282 【例4-13】奖金

首先我们知道想要给的奖金尽可能的少，那么我们就要每次发的时候尽可能的刚好满足不要发多了，当然也不要发少了否则会错。

那么我们可以想一个问题，这个题目构成的是不是一棵树呢？那看你比他大，她又比他大不会有换还联通不就是树吗？

那么既然是一棵树我们要的是发的奖金尽可能的小那么我们是不是因该根节点为100没往下走只多发1的奖金这样是不是最小呢？

那么我们的操作不就十分的简单了吗，我们就找到了那个发钱发最少的地方之后就慢慢往后找最后我们只要把所有的点的钱全部加起来并输出即可

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dep[1000005];
int in[1000005];
vector<int>E[100005];
queue<int>q;
int main(){
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i ++){
        int x,y;
        cin >> x >> y;
        E[y].push_back(x);
        in[x] ++;
    }
    bool f = 1;
    for(int i = 1 ; i <= n ; i ++){
        if(!in[i]){
            f = 0;
            q.push(i);
        }
    }
    if(f){
        cout << "Poor Xed" << endl;
        return 0;
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0 ; i < E[u].size() ; i ++){
            int v = E[u][i];
            dep[v] = max(dep[v] , dep[u] + 1);
            in[v] --;
            if(in[v] == 0){
                q.push(v);
            }
        }
    }
    int sum = 100 * n;
    for(int i = 1 ; i <= n ; i ++){
        sum += dep[i];
    }
    cout << sum;
    return 0;
}