【CCCC】L3-025 那就别担心了 (30分)，dfs搜索起点到终点的路径条数。

problem

L3-025 那就别担心了 (30分)
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。

ziqia.jpg

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有 3 条不同的推理路径。

输入格式：
输入首先在一行中给出两个正整数 N（1<N≤500）和 M，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1 S2，表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。

最后一行给出待检验的两个命题的编号 A B。

输出格式：
在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。

题目保证输出数据不超过 10
​9
​​ 。

输入样例 1：
7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1
输出样例 1：
3 Yes
输入样例 2：
7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1
输出样例 2：
3 No

solution

//给出n个点m条边的有向图，判断a到b有几条路，以及从a出发的终点是否都是b。
//先跑一遍dfs，维护从终点到点u的路径条数，答案为f[a]-f[b]。再跑一遍bfs，判断起点出发是否会到达从终点出发无法到达的点。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;

vector<int>G[maxn];

int s, t;
int f[maxn];//记忆化,维护从终点反向搜索到u的路径有几条
int dfs(int u){
	if(f[u])return f[u];
	if(u==t)return 1;
	for(int i = 0; i < G[u].size(); i++){
		int v = G[u][i];
		f[u] += dfs(v);
	}
	return f[u];
}

int ok=1;
int vis[510];
void bfs(){
	queue<int>q;
	q.push(s);
	while(q.size()){
		int tmp = q.front();  q.pop();
		if(vis[tmp])continue;
		vis[tmp] = 1;
		if(f[tmp]==0){
			ok = 0; break;
		}
		if(tmp==t)continue;
		for(int i = 0; i < G[tmp].size(); i++){
			int v = G[tmp][i];
			q.push(v);
		}
	}
}

int main(){
	int n, m;
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		int u, v;  cin>>u>>v;
		G[u].push_back(v);
	}
	cin>>s>>t;
	dfs(s);
	cout<<f[s]-f[t]<<" ";
	f[t] = 1;
	bfs();
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/111025895