pat顶级1008 Airline Routes （35 point(s)）

本文主要是介绍pat顶级1008 Airline Routes （35 point(s)），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎访问我的pat顶级题解目录哦 https://blog.csdn.net/richenyunqi/article/details/86751676

题目描述

算法设计

这是一道求解有向图的强连通分量的问题。可以采用Tarjan算法来求解。关于Tarjan算法可以参考维基百科Tarjan算法。下面直接给出代码实现。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=10005;
vector<int>graph[MAX];
//index[i]表示i是第几个被访问的结点,lowLink[i]表示从i出发经有向边可到达的所有节点中最小的index,sccno[i]表示i所属的强连通分量的编号
int index[MAX],lowLink[MAX],sccno[MAX],dfsNo=0,scc_cnt=0;
stack<int>s;
void DFS(int v){index[v]=lowLink[v]=++dfsNo;s.push(v);for(int i:graph[v]){if(index[i]==0){DFS(i);lowLink[v]=min(lowLink[v],lowLink[i]);}else if(sccno[i]==0)lowLink[v]=min(lowLink[v],index[i]);}if(lowLink[v]==index[v]){++scc_cnt;int t;do{t=s.top();s.pop();sccno[t]=scc_cnt;}while(t!=v);}
}
int main(){int n,m,k,a,b;scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&a,&b);graph[a].push_back(b);}for(int i=1;i<=n;++i)if(index[i]==0)DFS(i);scanf("%d",&k);while(k--){scanf("%d%d",&a,&b);puts(sccno[a]==sccno[b]?"Yes":"No");}return 0;
}

这篇关于pat顶级1008 Airline Routes （35 point(s)）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---