专栏文章

浅谈反图

rrxr2018360074
算法·理论参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mj5z5gst
此快照首次捕获于
2025/12/15 01:04
2 个月前
此快照最后确认于
2026/02/15 01:30
5 天前
查看原文
在做完这题后，我不禁陷入思考“反图”这个东西。以往，没有任何人给我详细讲过这种思想（虽然好像不需要讲），就好似幽灵一般凭空出现在了解题所需的方法当中，所以我们今天就来讲讲它。

何为反图

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

实现

极为简单，一般只用改一行。
原本：
CPP
for(int i=1;i<=m;i++){
  	int a,b;
  	cin>>a>>b;
    g[a].push_back(b);
}
现在：
CPP
for(int i=1;i<=m;i++){
    int a,b;
    cin>>a>>b;
    g[b].push_back(a);
}

应用

反图有一个重要的性质：如果在原图中 aa 可以到达 bb，在反图中 bb 就能到达 aa。所以一般情况下反图用于将多个点到一个点改为一个点到多个点，便于搜索。
例题一：给定一张 nn 个点 mm 条边的有向图，每个点有两种颜色：黑色与白色。有两种操作：将一个点染成黑色或查询某个点能否到达黑色点。给出 qq 次操作，对每种操作 22 输出结果。
1≤n,m,q≤1051\le n,m,q\le 10^5
解法：
显然，每一次都去从当前点搜过不了，所以考虑在操作 11 时储存答案，然后在操作 22 时直接查询。
但是，如果你考虑每个点能否到达黑点和暴力也没什么区别，所以我们从黑点的角度考虑。根据刚刚的结论，我们知道，只要反图上能从黑点走到某个点，那么在原图上就一定能从那个点走到黑点。
所以建立反图，加入黑点时用 BFS 搜索。
代码：
CPP
#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;
}
例题二：给定一张 nn 个点 mm 条边的有向无环图，边权均为 11，求每个点到 11 号点的路径数量。
思路：对于 DAG 上的 dp，我们一般采用拓扑序解决，但现在你同样无法一个个搜，所以考虑建立反图，因为一号在原图上不会有向其他点的边（有了直接删，反正没用），所以 11 号点的入度为 00，直接从 11 号开始搜。
讲一下一种可能的 Hack：如果某个点的出度为 00，那么它一定没用，这时要把它删去来保证拓扑排序能正常运行。
代码：
CPP
#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
*/

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...