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

推荐阅读

php
P1025 数的划分——简单题刷傻系列

P1025数的划分学傻了，学傻了，什么d ... [详细]

蜡笔小新 2023-10-17 17:56:50
email
gitlab重置password

ruby没怎么学，自己搭建的gitlab的rootpassword又忘了。幸好看见此帖子，试验okhttp:roland.kierkels.netgitreset-your-git ... [详细]

蜡笔小新 2023-10-17 22:22:07
php
机器学习算法代码实现——线性回归

前言：拿到一个案例，去分析：它该是做分类还是做回归，哪部分该做分类，哪部分该做回归，哪部分该做优化，它们的目标值分别是什么。再挑影响因素，哪些和分类有关的影响因素，哪些和回归有关的 ... [详细]

蜡笔小新 2023-10-17 19:58:52
数组
【费用流】【CODEVS】1227 方格取数2

【算法】最小费用最大流(费用流)【题解】费用流：http:www.cnblogs.comonioncycp6496532.html本题构图：在有限的k次 ... [详细]

蜡笔小新 2023-10-17 19:55:30
数组
运用kmp算法解决的一些问题的简单题解

学习kmp算法我最后是看的数据结构书上的一本教材学会的。。我觉得kmp相对于普通的BF算法就是避免了很多不必要的匹配，而kmp算法的精髓自然就在于next数组的运用。。。而next ... [详细]

蜡笔小新 2023-10-17 19:46:47
text
Flutter 布局（四） Baseline、FractionallySizedBox、IntrinsicHeight、IntrinsicWidth详解

本文主要介绍Flutter布局中的Baseline、FractionallySizedBox、IntrinsicHeight、IntrinsicWidth四种控件，详细介绍了其布局 ... [详细]

蜡笔小新 2023-10-17 18:17:09
text
[转载]从零开始学习OpenGL ES之四 – 光效

继续我们的iPhoneOpenGLES之旅，我们将讨论光效。目前，我们没有加入任何光效。幸运的是，OpenGL在没有设置光效的情况下仍然可 ... [详细]

蜡笔小新 2023-10-17 17:38:05
function
web标准(复习)8

今天我们开始学习下拉及多级弹出菜单，包含以下内容和知识点：带下拉子菜单的导航菜单绝对定位和浮动的区别和运用css自适应宽度滑动门菜单一、带下拉子菜单的导航菜单下拉菜单在一些 ... [详细]

蜡笔小新 2023-10-17 20:57:32
function
Simple Tips on C++(对于C++的一些建议)

Introduction（简介）Forbeingapowerfulobject-orientedprogramminglanguage,Cisuseda ... [详细]

蜡笔小新 2023-10-17 19:48:02
数组
开发笔记:DDecrease (Contestant ver.) AtCoder2661

本文由编程笔记#小编为大家整理，主要介绍了D-Decrease(Contestantver.)AtCoder-2661相关的知识，希望对你有一定的参考价值。 ... [详细]

蜡笔小新 2023-10-17 19:16:23
数组
设备模型三（潜谈sysfs）

前言引出一个问题：假设sysaxx,xx是kobja的属性文件,当对xx进行写操作时,即echo‘1’sysaxx实际上,调用了kobja的ktype中定义的接口函 ... [详细]

蜡笔小新 2023-10-17 19:01:26
数组
arraylist和linkedlist内部的实现大致是怎样的

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 2.对于随机访问get和set，ArrayList优于LinkedList，因为Ar ... [详细]

蜡笔小新 2023-10-17 19:00:38
数组
c# 联合halcon 基于相关性模板匹配_HALCON形状匹配详解

点击上方“新机器视觉”，选择加”星标”或“置顶”重磅干货，第一时间送达很早就想总结一下前段时间学习HALCON的心得，但由于其他的事情总是抽不出时间。去年有过一段时间的集中学习，做 ... [详细]

蜡笔小新 2023-10-17 18:47:00
数组
【论文】ICLR 2020 九篇满分论文！！！

点击上方，选择星标或置顶，每天给你送干货！阅读大概需要11分钟跟随小博主，每天进步一丢丢来自：深度学习技术前沿 ... [详细]

蜡笔小新 2023-10-17 18:45:53
数组
【AcWing】学了一坤时才明白的一道题

🎆音乐分享（点击链接可以听哦） ... [详细]

蜡笔小新 2023-10-17 17:35:11

WSSDRED_935

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

Tags | 热门标签

RankList | 热门文章