浅谈反图

· · 算法·理论

在做完这题后，我不禁陷入思考“反图”这个东西。以往，没有任何人给我详细讲过这种思想（虽然好像不需要讲），就好似幽灵一般凭空出现在了解题所需的方法当中，所以我们今天就来讲讲它。

何为反图

顾名思义，返图就是和题目中的输入反着来（有向图），如果题目说 a\to b，那么在图上就 b\to a。

实现

极为简单，一般只用改一行。

原本：

for(int i=1;i<=m;i++){
    int a,b;
    cin>>a>>b;
    g[a].push_back(b);
}

现在：

for(int i=1;i<=m;i++){
    int a,b;
    cin>>a>>b;
    g[b].push_back(a);
}

应用

反图有一个重要的性质：如果在原图中 a 可以到达 b，在反图中 b 就能到达 a。所以一般情况下反图用于将多个点到一个点改为一个点到多个点，便于搜索。

例题一：给定一张 n 个点 m 条边的有向图，每个点有两种颜色：黑色与白色。有两种操作：将一个点染成黑色或查询某个点能否到达黑色点。给出 q 次操作，对每种操作 2 输出结果。

1\le n,m,q\le 10^5

解法：

显然，每一次都去从当前点搜过不了，所以考虑在操作 1 时储存答案，然后在操作 2 时直接查询。

但是，如果你考虑每个点能否到达黑点和暴力也没什么区别，所以我们从黑点的角度考虑。根据刚刚的结论，我们知道，只要反图上能从黑点走到某个点，那么在原图上就一定能从那个点走到黑点。

所以建立反图，加入黑点时用 BFS 搜索。

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> g[1000000];
bool can[1000000];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        g[b].push_back(a);
    }
    int q;
    cin>>q;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int v;
            cin>>v;
            if(can[v]){
                continue;
            }
            can[v]=1;
            queue<int> q;
            q.push(v);
            while(q.size()){
                int t=q.front();
                q.pop();
                for(auto d:g[t]){
                    if(can[d]){
                        continue;
                    }
                    q.push(d);
                    can[d]=1;
                }
            }
        }
        else{
            int v;
            cin>>v;
            cout<<(can[v]?"Yes":"No")<<endl;
        }
    }
    return 0;
}

例题二：给定一张 n 个点 m 条边的有向无环图，边权均为 1，求每个点到 1 号点的路径数量。

思路：对于 DAG 上的 dp，我们一般采用拓扑序解决，但现在你同样无法一个个搜，所以考虑建立反图，因为一号在原图上不会有向其他点的边（有了直接删，反正没用），所以 1 号点的入度为 0，直接从 1 号开始搜。

讲一下一种可能的 Hack：如果某个点的出度为 0，那么它一定没用，这时要把它删去来保证拓扑排序能正常运行。

代码：


#include<bits/stdc++.h>
using namespace std;
vector<int> g[1000000];
int in[1000000];
long long dp[1000000];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(a==1){ //特判1:1出去的边一定没用
            continue;
        }
        g[b].push_back(a);
        in[a]++;
    }
    for(int i=2;i<=n;i++){
        if(in[i]==0){
            for(auto v:g[i]){
                in[v]--;
            }
        }
    } //特判2：入度为零的点直接删
    queue<int> q;
    dp[1]=1;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            dp[v]+=dp[u];
            in[v]--;
            if(in[v]==0){
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<" ";
    }
    return 0;
}
/*
Hack
7 10
1 5
5 6
2 1
3 1
2 3
4 2
4 3
2 7
3 7
4 7

1 2 1 3 0 0 0
*/