用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 ;
}

最新文章

  1. [工具] GIF 动画每帧合并到一张 PNG
  2. 有关segue的简介
  3. SegmentFault创始人高阳:辍学后带着500元北漂,4年建成国内最大开发者
  4. ios开发之触碰动画效果
  5. 关于JAVA那点事---i++和++i
  6. 判断String为空
  7. Spring3 + Spring MVC+ Mybatis 3+Mysql 项目整合(注解及源码)
  8. yii2的安装使用
  9. BOOST 线程完全攻略 - 结束语
  10. java之观察者模式
  11. WOJ 1014
  12. AI 人工智能 探索 (九)
  13. C++实现的控制台-贪吃蛇
  14. ABP从入门到精通(5):使用基于JWT标准的Token访问WebApi
  15. JS小游戏:贪吃蛇(附源码)
  16. 数据库面试题目- ORACLE
  17. MediaManager配置公网访问功能
  18. centOS设置开机自启
  19. 正益工作能担起PaaS+SaaS的未来探索吗?
  20. JQ 实现轮播图(3D旋转图片轮播效果)

热门文章

  1. Go_type
  2. [经验] Java 使用 netty 框架, 向 Unity 客户端的 C# 实现通信[2]
  3. PHP 文件上传之如何识别文件伪装?——PHP的fileinfo扩展可!
  4. Git远程推送和抓取分支
  5. python中的基本类型
  6. wampserver3.0.6 外网 不能访问
  7. mac系统,docker下载安装
  8. Spring boot security权限管理集成cas单点登录
  9. 洛谷 P1043 数字游戏(区间dp)
  10. Ansible自动化搭建及工具集和常见模块、命令详情(重点)