BFS+强连通。输出max(缩点后出度为0的点数,缩点后入度为0的点数)。

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
#include <algorithm>
#define LL unsigned __int64
using namespace std; const int N= ; struct Edge{
int u,v;
int next;
}edge[N*];
int tot,index;
int head[N],dfn[N],low[N],stack[N],st;
int outdegree[N],indegree[N];
int belong[N],beg;
bool instack[N];
int map[][]; int dir[][]={
{,},
{,-},
{,},
{-,}
}; void addedge(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
} void Tarjan(int u) {
dfn[u]=low[u]=++index;
stack[st++]=u;
instack[u]=true;
for(int e=head[u];e!=-;e=edge[e].next){
int v=edge[e].v;
if (dfn[v]==-) {
Tarjan(v) ;
low[u] = min(low[u], low[v]) ;
}
else if (instack[v]) {
low[u] = min(low[u], dfn[v]) ;
}
}
int v;
if (dfn[u] == low[u]) {
beg++;
outdegree[beg]=indegree[beg]=;
do{
v=stack[--st];
belong[v]=beg;
instack[v]=false;
}while(u!= v);
}
} bool ok(int i,int j,int x,int y){
if(i>=&&i<x&&j>=&&j<y) return true;
return false;
} int main(){
int x,y;
while(scanf("%d%d",&y,&x)!=EOF){
for(int i=;i<x;i++){
for(int j=;j<y;j++)
scanf("%d",&map[i][j]);
} tot=index=st=beg=;
int u,v,tx,ty;
int spoint=x*y;
for(int i=;i<=spoint;i++){
head[i]=dfn[i]=low[i]=belong[i]=-;
instack[i]=false;
} for(int i=;i<x;i++){
for(int j=;j<y;j++){
u=i*y+j;
for(int k=;k<;k++){
tx=i+dir[k][];
ty=j+dir[k][];
if(ok(tx,ty,x,y)){
if(map[tx][ty]<=map[i][j]){
v=tx*y+ty;
addedge(u,v);
}
}
}
}
} for(int i=;i<spoint;i++){
if(dfn[i]==-){
Tarjan(i);
}
} for(int i=;i<spoint;i++){
u=i;
for(int e=head[u];e!=-;e=edge[e].next){
v=edge[e].v;
if(belong[u]!=belong[v]){
outdegree[belong[u]]++;
indegree[belong[v]]++;
}
}
} int ou=,in=;
if(beg==){
puts("");
continue;
}
for(int i=;i<=beg;i++){
if(outdegree[i]==){
ou++;
}
if(indegree[i]==)
in++;
} printf("%d\n",max(ou,in));
}
return ;
}

最新文章

  1. PHP笔记(PHP初级篇)
  2. 传入的表格格式数据流(TDS)远程过程调用(RPC)协议流不正确。此 RPC 请求中提供了过多的参数。最多应为 2100
  3. 1017作业:配置java环境,学习流程图
  4. Ubuntu连接L2TP的VPN设置
  5. Oracle数据库中文乱码问题
  6. MyEclipse里项目部署到tomcat上之后,tomcat webpps文件夹里为什么找不到这个项目
  7. 7z文件格式及其源码的分析
  8. POJ 3254 Corn Fields:网格密铺类 状压dp
  9. struts2系列(四):struts2国际化的多种方式
  10. GC参考手册 —— GC 调优(工具篇)
  11. robotframework-databaselibrary安装步骤
  12. Java并发编程:Synchronized底层优化(偏向锁、轻量级锁)
  13. jquery动态添加元素无法触发绑定的事件的解决方案
  14. PHP下进行XML操作(创建、读取)
  15. [右键]如何添加Sublime为右键菜单
  16. mysql时间格式化函数日期格式h和H区别
  17. 如何用原生js替换字符串中的某个字符(或字符串)为指定的字符串?
  18. 「小程序JAVA实战」运行微信官方demo(四)
  19. Struts2中Action自己主动接收參数
  20. Reset CSS 页面初始化css

热门文章

  1. 二维矩阵相乘 in C++
  2. (Go)07.Go语言中strings和strconv包示例代码详解01
  3. php的get_object_vars函数
  4. Python 43 视图 、sql注入问题 、事务 、存储过程
  5. Python 38 sql基础
  6. tpshop编辑框中上传图片过大变模糊
  7. CentOS7 搭建Kafka(三)工具篇
  8. linux下常用命令失效
  9. javascript事件绑定1-模拟jquery可爱的东西
  10. P1146 硬币翻转