PAT T1008 Airline Routes
2024-09-04 03:40:19
用tarjan算法缩点~
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
vector<int> g[maxn];
int N,M,x,y;
int low[maxn];
int dfn[maxn];
int cnt;
int pos[maxn];
int scc;
stack<int> st;
void tarjan (int x) {
low[x]=dfn[x]=++cnt;
st.push(x);
for (int i=;i<g[x].size();i++) {
if (!low[g[x][i]]) {
tarjan (g[x][i]);
low[x]=min(low[x],low[g[x][i]]);
}
else if (!pos[g[x][i]]) low[x]=min(low[x],dfn[g[x][i]]);
}
if (low[x]==dfn[x]) {
scc++;
while () {
int u=st.top();
st.pop();
low[u]=low[x];
pos[u]=scc;
if (u==x) break;
}
}
}
int main () {
scanf ("%d %d",&N,&M);
for (int i=;i<M;i++) {
scanf ("%d %d",&x,&y);
g[x].push_back(y);
}
for (int i=;i<=N;i++)
if (!low[i]) tarjan(i);
scanf ("%d",&M);
for (int i=;i<M;i++) {
scanf ("%d %d",&x,&y);
printf ("%s\n",low[x]==low[y]?"Yes":"No");
}
return ;
}
最新文章
- [工具] GIF 动画每帧合并到一张 PNG
- 有关segue的简介
- SegmentFault创始人高阳:辍学后带着500元北漂,4年建成国内最大开发者
- ios开发之触碰动画效果
- 关于JAVA那点事---i++和++i
- 判断String为空
- Spring3 + Spring MVC+ Mybatis 3+Mysql 项目整合(注解及源码)
- yii2的安装使用
- BOOST 线程完全攻略 - 结束语
- java之观察者模式
- WOJ 1014
- AI 人工智能 探索 (九)
- C++实现的控制台-贪吃蛇
- ABP从入门到精通(5):使用基于JWT标准的Token访问WebApi
- JS小游戏:贪吃蛇(附源码)
- 数据库面试题目- ORACLE
- MediaManager配置公网访问功能
- centOS设置开机自启
- 正益工作能担起PaaS+SaaS的未来探索吗?
- JQ 实现轮播图(3D旋转图片轮播效果)
热门文章
- Go_type
- [经验] Java 使用 netty 框架, 向 Unity 客户端的 C# 实现通信[2]
- PHP 文件上传之如何识别文件伪装?——PHP的fileinfo扩展可!
- Git远程推送和抓取分支
- python中的基本类型
- wampserver3.0.6 外网 不能访问
- mac系统,docker下载安装
- Spring boot security权限管理集成cas单点登录
- 洛谷 P1043 数字游戏(区间dp)
- Ansible自动化搭建及工具集和常见模块、命令详情(重点)