• 112737

    文章

  • 803

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

PAT顶级 1008 Airline Routes (35分)(有向图的强连通分量)

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>
欢迎大家访问我的PAT TOP解题目录~

https://blog.csdn.net/qq_45228537/article/details/103671868

题目链接:

1008 Airline Routes (35分)



思路:

将有向图分为若干强连通分量的裸题
使用正反dfs的Kosaraju算法或者效率高一些、一次dfs的Tarjan算法即可;




代码:





#include<bits/stdc++.h>

using namespace std;

const int maxn = 12345;
int dfn, scc_cnt, num[maxn], low[maxn], sccno[maxn];
vector<int> G[maxn];
stack<int> stk;

void dfs(int u){
	stk.push(u);
	num[u] = low[u] = ++dfn;
	for(int& v : G[u]){
		if(!num[v]) dfs(v), low[u] = min(low[u], low[v]);	
		else if(!sccno[v]) low[u] = min(low[u], num[v]);
	}
	if(low[u] == num[u]){
		++scc_cnt;
		for(;;){
			int v = stk.top(); stk.pop();
			sccno[v] = scc_cnt;
			if(u == v) break;	
		}
	}
}
int main(){
#ifdef MyTest
	freopen("Sakura.txt", "r", stdin);
#endif
	int n, m, k;
	scanf("%d %d", &n, &m);
	while(m--){
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y);
	}
	for(int i = 1; i <= n; i++) if(!num[i]) dfs(i);
	scanf("%d", &k);
	while(k--){
		int x, y; scanf("%d %d", &x, &y);
		if(sccno[x] == sccno[y]) puts("Yes");
		else puts("No");	
	}
	return 0;
}

695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客