http://acm.hdu.edu.cn/showproblem.php?pid=3594

题意:

一个有向图,判断是否强连通和每条边只在一个环中。

思路:

仙人掌问题。

用Tarjan算法判断强连通分量的时候,记录每节结点的父节点。当找到一个环后,回溯将该环上的所有结点+1,如果有结点出现2次了,则说明不是仙人掌了。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
using namespace std; const int maxn=+; int n,m; vector<int> G[maxn];
int in[maxn];
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
int fa[maxn]; int find(int u,int v)
{
while(fa[u]!=v)
{
in[u]++;
if(in[u]>) return ;
u=fa[u];
}
return ;
} int dfs(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
for(int i=;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
fa[v]=u;
if(!dfs(v)) return ;
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v])
{
lowlink[u]=min(lowlink[u],pre[v]);
if(!find(u,v)) return ;
}
}
if(lowlink[u]==pre[u])
{
scc_cnt++;
if(scc_cnt>) return ;
}
return ;
} int find_scc()
{
dfs_clock=scc_cnt=;
memset(sccno,,sizeof(sccno));
memset(pre,,sizeof(pre));
memset(in,,sizeof(in));
memset(fa,,sizeof(fa));
for(int i=;i<n;i++)
if(!pre[i]) if(!dfs(i)) return ;
return ;
} int main()
{
//freopen("D:\\input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<n;i++) G[i].clear();
while(true)
{
int u,v;
scanf("%d%d",&u,&v);
if(u== && v==) break;
G[u].push_back(v);
}
if(find_scc() && scc_cnt==) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}

最新文章

  1. STM32 C语言,端口映射
  2. java-a实现压缩与解压缩(zip、gzip)
  3. [hdu1394]Minimum Inversion Number(树状数组)
  4. Redis安装及HA(High Availability)配置
  5. Unity3D面试题汇总
  6. Redis基础知识之—— 5个必须了解的事情【★★★★★】
  7. python3抓取异步百度瀑布流动态图片(二)get、json下载代码讲解
  8. ADF_Advanced ADF系列1_Fusion应用的客制和个性化(Part1)
  9. [译]rabbitmq 2.5 Where’s my message? Durability and you
  10. The ObjectContext instance has been disposed and can no longer be used for operations that require a connection.
  11. 高性能WEB开发 为什么要减少请求数,如何减少请求数!
  12. 批量的单向的ssh 认证
  13. mui 访问手机自带是否连接网络
  14. Google HTML/CSS 编码规范
  15. Python 第五天
  16. Django Form表单学习总结
  17. mysql(2)—— 由笛卡尔积现象分析数据库表的连接
  18. 【常用配置】Spring框架web.xml通用配置
  19. Ubuntu 14.04 执行指定用户的命令
  20. #001 WebStrom SVN使用技巧

热门文章

  1. Django1.6 运行manage.py 报错解决办法(ImportError)
  2. 未安装git lfs导致git下载不完整,没有错误提示
  3. vim 设置字体和解决乱码
  4. CloudFoundry V2 单机版离线安装(伪离线安装)
  5. js-jquery-001-条形码概述
  6. Spring框架第五篇之Spring与AOP
  7. SuperObject使用
  8. Django:学习笔记(8)——视图
  9. cdoj1633 去年春恨却来时,落花人独立,微雨燕双飞
  10. [转]loadrunner:系统的平均并发用户数和并发数峰值如何估算