hdu1269强连通+并查集

作者：WSSDRED_935 | 来源：互联网 | 2023-09-25 21:10

这是一道典型的强连通的题目。所谓强连通，就是对于一个有向图，若一个集合内任意2点都能过互相达，于是这个几何就是一个强连通分量。对于任意图，都可以分解人多个不相交的强连通集合。

这是一道典型的强连通的题目。所谓强连通，就是对于一个有向图，若一个集合内任意2点都能过互相达，于是这个几何就是一个强连通分量。对于任意图，都可以分解人多个不相交的强连通集合。对于这题目，只要用著名的tarjin算法对原图进行一次强连通缩点，若说有点都在一个强连通分量，就是yes，否者no。这里可以用并查集。

VIEW CODE

//#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax= 10010;
const int mod=1000000007;
struct node
{
int st,en;
int next;
}E[100010];
int p[mmax],fa[mmax];
int num;
void init()
{
memset(p,-1,sizeof p);
num=0;
}
void add(int st,int en)
{
E[num].st=st;
E[num].en=en;
E[num].next=p[st];
p[st]=num++;
}
int find(int x)
{
if(x==fa[x])
return x;
return fa[x]=find(fa[x]);
}
int times,pp;
int low[mmax],dfn[mmax],Q[mmax];
bool instack[mmax];
void tarjin(int u)
{
dfn[u]=low[u]=++times;
Q[++pp]=u;
instack[u]=1;
for(int i=p[u];i+1;i=E[i].next)
{
int v=E[i].en;
if(!dfn[v])
{
tarjin(v);
if(low[u]>low[v])
low[u]=low[v];
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
while(pp)
{
int x=Q[pp--];
instack[x]=0;
if(x==u)
break;
int xx=find(x);
fa[xx]=u;
}
}
}
int main()
{
int n,m;
while(cin>>n>>m && n+m)
{
init();
times=pp=0;
memset(dfn,0,sizeof dfn);
memset(instack,0,sizeof instack);
for(int i=0;i<=n;i++)
fa[i]=i;
for(int i=0;i {
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjin(i);
int cnt=0;
for(int i=1;i<=n;i++)
if(i==find(i))
cnt++;
if(cnt-1)
puts("No");
else
puts("Yes");
}
return 0;
}

推荐阅读

main
CF865D

这道贪心非常神仙大体想法肯定是选择一个价格较低的一天买入并在之后找一个价格较高的一天卖出直接贪心的选显然不可行，考虑如何实现“反悔”这里直接说做法，反正我也想不到从前向后扫描每一天 ... [详细]

蜡笔小新 2024-10-09 08:34:52
main
Ⅴ 运算符重载

1.从函数重载到运算符重载1.1多态性?使用一致的接口（uniforminterface）处理不同类型的数据?例子:运算符重载（+）3.14+0.00153.1415[1,2,3] ... [详细]

蜡笔小新 2024-10-10 13:57:35
text
计算字体高度

letstr:NSString真正的娱乐是应着真正的工作的要求而发生的。冰心成功的花，人们只惊慕她现时的明艳!然而当初她的芽儿，浸透了奋斗的泪泉，洒遍了牺牲的血雨。冰心青春活泼的 ... [详细]

蜡笔小新 2024-10-10 12:24:41
text
kvm usb2.0

Virt-Manageraddssupportforusb2Wednesday,April4,2012-10:40HaydnSolomonThemostrecentreleaseo ... [详细]

蜡笔小新 2024-10-09 17:15:12
main
解题：洛谷2093 JZPFAR

题面初见K-DTree其实这样的题(欧几里得距离第$x$近点对)不应该用K-DTree做，因为会被构造数据卡成$O(n^2)$，随机的另说。但是并没有找 ... [详细]

蜡笔小新 2024-10-08 19:25:45
function
页面刷新 location.reload()

*页面不刷新，但是加了location.reload()后，把炒作失败提示语都刷没了。成功，不提示，刷新看数据变化ajaxsuccess:function(res){if(res. ... [详细]

蜡笔小新 2024-10-10 21:27:59
main
希尔排序(Shell Sort)学习（四）

希尔排序(ShellSort)基本思想：　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直 ... [详细]

蜡笔小新 2024-10-10 11:01:24
tree
通过安卓手机获取微信小程序包进行反编译方法

偶然有需求了解别人的小程序实现方法，网上相关资料很多，顺便了解了一下，做个总结，没啥技术含量，分享出来。要求安装Nodejs一台root后的安卓手机或者装有可以打开微信小程序的安卓 ... [详细]

蜡笔小新 2024-10-10 07:15:00
object
一数据结构入门

基本概念有哪些数据结构?有哪些数据结构?线性表，栈，队列，串，数组，广义表，树，二叉树，图重点是线性表，二叉树每种数据结构需要掌握，添加、更新、删除、查询、排序等操作的实现学习数据 ... [详细]

蜡笔小新 2024-10-09 21:27:43
object
.net core docker+ gogs + jenkins 自动化部署

一.安装gogs1.拉取gogs镜像dockerpullgogsgogs2.运行gogs容器dockerrun-di--namegogs-p10022:22-p3000:3000- ... [详细]

蜡笔小新 2024-10-09 20:41:46
input
极限定律 My Algorithm Space AC自动机算法详解

转载自：http:www.cppblog.commythitarchive2009042180633.html首先简要介绍一下AC自动机：Aho-Corasickautomation ... [详细]

蜡笔小新 2024-10-09 20:36:54
text
js大量计算导致dom被阻塞

不知道有没有人遇到过这种为题，如下代码 ... [详细]

蜡笔小新 2024-10-09 19:44:19
input
方阵|回路_HDU2859 Phalanx(动态规划/哈希表)

篇首语：本文由编程笔记#小编为大家整理，主要介绍了HDU-2859Phalanx(动态规划/哈希表)相关的知识，希望对你有一定的参考价值。题目链接：点 ... [详细]

蜡笔小新 2024-10-09 15:39:10
main
Android性能优化检测App卡顿

在移动APP性能评测-流畅度评测中，我们介绍了如何准确客观评价APP的流畅度，最终采用SM指标来评价应用的流畅度，在知道如何评价流畅度之后 ... [详细]

蜡笔小新 2024-09-30 15:39:41
main
2022杭电多校七 FSumire（数位DP+实用技巧）

题目链接：杭电多校7-VirtualJudgevjudge上题目显示的有问题，我下面附上官方题目：样例输入：32201 ... [详细]

蜡笔小新 2024-09-30 10:31:00

WSSDRED_935

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章