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

推荐阅读

include
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
include
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
io
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
char
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
char
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
include
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
io
知识图谱——机器大脑中的知识库

本文介绍了知识图谱在机器大脑中的应用，以及搜索引擎在知识图谱方面的发展。以谷歌知识图谱为例，说明了知识图谱的智能化特点。通过搜索引擎用户可以获取更加智能化的答案，如搜索关键词"Marie Curie"，会得到居里夫人的详细信息以及与之相关的历史人物。知识图谱的出现引起了搜索引擎行业的变革，不仅美国的微软必应，中国的百度、搜狗等搜索引擎公司也纷纷推出了自己的知识图谱。 ... [详细]

蜡笔小新 2023-12-14 10:06:19
io
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
io
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
include
指针的引用以及在什么情况下使用指针的引用

本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]

蜡笔小新 2023-12-13 12:54:29
char
猜字母游戏

猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]

蜡笔小新 2023-12-13 12:04:03
io
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
include
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
include
Mac OS 升级到11.2.2 Eclipse打不开了，报错Failed to create the Java Virtual Machine

本文介绍了在Mac OS升级到11.2.2版本后，使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题，并提供了解决方法。 ... [详细]

蜡笔小新 2023-12-14 12:01:13
io
JVM 学习总结（三）——对象存活判定算法的两种实现

本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法：引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活，虽然简单高效，但无法解决循环引用的问题；可达性分析算法通过判断对象是否可达来确定存活对象，是主流的Java虚拟机内存管理算法。 ... [详细]

蜡笔小新 2023-12-13 18:59:46

WSSDRED_935

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

Tags | 热门标签

RankList | 热门文章