51Nod--1076 2条不相交的路径(强连通分量)
2024-08-30 18:22:01
#include<bits/stdc++.h> using namespace std; #define LL long long #define maxn 30000 vector<int>q[maxn]; int dfn[maxn],low[maxn],st[maxn],vis[maxn],top; int num[maxn],i; void dfs(int u,int deep,int fa){ dfn[u]=deep; low[u]=deep; st[++top]=u; vis[u]=; ;j<q[u].size();j++){ int v=q[u][j]; if(v==fa) continue; if(!dfn[v]){ dfs(v,deep+,u); low[u]=min(low[u],low[v]); }else if(vis[v]){ low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]){ num[u]=++i; vis[u]=; while(st[top]!=u){ num[st[top]]=i; vis[st[top]]=,top--; } top--; } } int main(){ int n,m; cin>>n>>m; memset(vis,,sizeof(vis)); memset(dfn,,sizeof(dfn)); ;j<m;j++){ int u,v; scanf("%d%d",&u,&v); q[u].push_back(v); q[v].push_back(u); } top=,i=; ;j<=n;j++){ if(!dfn[j]){ dfs(j,,j); } } int z; cin>>z; ;j<z;j++){ int u,v; scanf("%d%d",&u,&v); if(num[u]==num[v]){ printf("Yes\n"); }else{ printf("No\n"); } } ; }
最新文章
- Linux截屏工具scrot用法详细介绍
- jekyll安装的斗智斗勇
- monkey学习笔记
- python的反射机制
- web设计经验<;三>;值得你深入了解的交互设计5大支柱
- Android 批量插入数据到SQLite数据库
- C++与Lua交互(四)
- 【恒天云】OpenStack和CloudStack对比研究报告
- BZOJ 3514 (动态树)
- 用java实现Simsimi小黄鸡接口
- Maximum Subarray (JAVA)
- 五大科技巨头VR/AR专利报告,Magic Leap以22.6%领跑
- BBED跳过归档
- Time complexity of ArrayList in Java
- iOS&#183;UIKit框架注解 &; Foundation
- idea 配置tomcat(包含tomcat Server找不到的配置方法)
- 【学习笔记】tensorflow文件读取
- idea常用操作大全
- CITROEN C8 BSI HC12 Mileage Correction with Digiprog3
- 算法bug修复