强连通 HDU 1269

时间:2022-10-27 07:43:49

n点m边

求是否能从任意a->b b->a

强连通分量等于1

 #include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h>
#include<stack> using namespace std; #define MAXN 100010 int head[MAXN],low[MAXN],dfn[MAXN],f[MAXN];
bool vis[MAXN];
int cnt,k,num;
struct edg
{
int fr,to,next; }x[MAXN]; void add(int u,int v)
{
x[cnt].next=head[u];
x[cnt].fr=u;
x[cnt].to=v;
head[u]=cnt++;
}
stack<int>s; void dfs(int u)
{
low[u]=dfn[u]=k++;
vis[u]=;
s.push(u);
int i;
for(i=head[u];i!=-;i=x[i].next)
{
int t=x[i].to;
if(!dfn[t])
{
dfs(t);
low[u]=min(low[u],low[t]);
}
else if(vis[t])
low[u]=min(low[u],dfn[t]);
}
if(low[u]==dfn[u])
{
num++;
while(!s.empty())
{
int now=s.top();
s.pop();
vis[now]=;
f[now]=num;
if(now==u)break;
}
}
}
int main()
{
int n,m; while(scanf("%d%d",&n,&m)!=EOF)
{
if(n+m==)
break;
int i;
memset(head,-,sizeof(head));
cnt=;
for(i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
k=;
num=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
for(i=;i<=n;i++)
{
if(!dfn[i])
dfs(i);
}
if(num==)
printf("Yes\n");
else
printf("No\n");
}
return ;
}

强连通 HDU 1269的更多相关文章

  1. HDU 1269 迷宫城堡(强连通)

    HDU 1269 迷宫城堡 pid=1269" target="_blank" style="">题目链接 题意:中文题 思路:强连通模板题 代 ...

  2. Hdu 1269 强连通判定

    题目链接 迷宫城堡 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total S ...

  3. HDU 1269 迷宫城堡 &lpar;Kosaraju&rpar;

    题目链接:HDU 1269 Problem Description 为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000), ...

  4. hdu - 1269 迷宫城堡 &lpar;强连通裸题&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=1269 判断一个图是不是强连通,缩点之后判断顶点数是不是为1即可. #include <iostream&g ...

  5. HDU 1269:迷宫城堡(强连通)

    http://acm.hdu.edu.cn/showproblem.php?pid=1269 题意:确定是否是一个强连通图. 思路:裸的tarjan算法. #include <cstdio&gt ...

  6. HDU 1269 迷宫城堡(判断有向图强连通分量的个数,tarjan算法)

    迷宫城堡 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  7. hdu 1269 迷宫城堡 强连通分量

    迷宫城堡 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  8. HDU 1269 迷宫城堡 (强连通分量,常规)

    题意: 判断所给的有向图是否是一个强连通图. 思路: 如果连通分量大于1则必定No,如果强连通分量大于1也是No.tarjan算法求强连通分量. #include <cstdio> #in ...

  9. HDU 1269 迷宫城堡 tarjan算法求强连通分量

    基础模板题,应用tarjan算法求有向图的强连通分量,tarjan在此处的实现方法为:使用栈储存已经访问过的点,当访问的点离开dfs的时候,判断这个点的low值是否等于它的出生日期dfn值,如果相等, ...

随机推荐

  1. C&plus;&plus;实现Ping

    这是一个老话题了,但是我刚学会... 我们的目的是实现这么个东西: 之所以用红框框一下是因为,从baidu.com到123.125.114.144的过程是DNS解析,我们暂时先实现ping的部分. 基 ...

  2. October 20th Week 43rd Thursday&comma; 2016

    Now, it's clear. OPPO R9s 这一刻 更清晰. I want a new mobile phone, because the one I am using is broken. ...

  3. 【Oracle】oracle之listagg分析函数

    oracle分析函数——listagg篇 (1)使用listagg将多行数据合并到一行 例表: select deptno, ename from emp order by deptno, ename ...

  4. input上传按钮 文字修改办法

    解决思路是把input 放在文字的上边,弄成透明的,这样在点文字时,实际是点击了input,这样就实现了文件的上传. 具体代码: <style> #uploadImg{ font-size ...

  5. 【Java基础】关于String的总结

    String构造方法初始化和常量赋值初始化区别 下面的代码是一个String对象的两种不同的初始化方式,关于这两种不同初始化方式的区别,本文通过画内存图来进行解释,首先代码如下: public cla ...

  6. SQL语句查询某字段不同数据的个数(DISTINCT 的使用)

    今天做了一个题,学到了一个知识点: 有一个高速收费表VF,如下: 统计收费涉及的车辆有多少: SQL语句: SELECT  COUNT(DISTINCT  VchReg)  from  VF ; 其中 ...

  7. jasperreport

     我们的报表要用FusionCharts.jasperreport

  8. Component Interface相关面试题

    下面的列表中的问题很常见,Component Interface是很重要的.你知道基本知识比知道答案更重要. Q:以下陈述是错误的. A:一个Component Interface 可以map多个Pe ...

  9. django框架--路由系统

    目录 一.路由系统理解 二.路由系统功能划分 三.路由表创建 创建工具 二级路由 路由别名 动态路由及重定向 四.自定义错误页面 五.图示路由系统在框架中的定位 六.路由系统的进阶想法 一.路由系统理 ...

  10. Wampserver环境配置

    ☆根目录修改问题 /.修改运行根目录 1.修改apache配置,将服务请求定位到新目录下 →左击wampserver,点击Apache打开httpd.conf文件,Ctrl+f搜索documentro ...