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

推荐阅读

string
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

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

蜡笔小新 2023-12-14 18:18:21
string
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

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

蜡笔小新 2023-12-14 15:08:18
string
Hibernate基础映射

在说Hibernate映射前，我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象，以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]

蜡笔小新 2023-12-14 10:57:47
string
知识图谱——机器大脑中的知识库

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

蜡笔小新 2023-12-14 10:06:19
string
后台获取视图对应的字符串

1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注：不会执行对应的ac ... [详细]

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

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

蜡笔小新 2023-12-13 16:16:05
string
Java实现大数乘法（分治算法）

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

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

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

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

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

蜡笔小新 2023-12-14 12:09:13
import
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
string
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
spring
SpringBoot集成前端模版（thymeleaf）的配置步骤

本文介绍了在SpringBoot中集成thymeleaf前端模版的配置步骤，包括在application.properties配置文件中添加thymeleaf的配置信息，引入thymeleaf的jar包，以及创建PageController并添加index方法。 ... [详细]

蜡笔小新 2023-12-14 10:11:46
php
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
string
java 线程死锁模拟

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

蜡笔小新 2023-12-13 19:12:25
php
基于layUI的图片上传前预览功能的2种实现方式

本文介绍了基于layUI的图片上传前预览功能的两种实现方式：一种是使用blob+FileReader，另一种是使用layUI自带的参数。通过选择文件后点击文件名，在页面中间弹窗内预览图片。其中，layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块，并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]

蜡笔小新 2023-12-14 17:06:58

WSSDRED_935

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

Tags | 热门标签

RankList | 热门文章