博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
题解 P2863 【[USACO06JAN]牛的舞会The Cow Prom】
阅读量:4313 次
发布时间:2019-06-06

本文共 1572 字,大约阅读时间需要 5 分钟。

赤裸裸的板子,就加一个特判就行。直接上代码

#include
#include
#include
using namespace std;bool ins[10000000];//记录入没入栈。bool typ[10000000];//特判*1,是强连通分量就直接过了。int top;int ans[10000000];int stack[10000000];//手写栈。void push(int x)//手写栈ing.{ ins[x]=true; stack[++top]=x; return ;}void pop(){ ins[stack[top]]=false; top--; return ;}struct data{ int v;int next;}edge[10000000];int cnt;int alist[10000000];void add(int u,int v)//继续手写结构体。{ edge[++cnt].v=v; edge[cnt].next=alist[u]; alist[u]=cnt;}int dfn[100000];int dfu;//dfn作为x的入栈序号。int low[1000000];int res=0;void dfs(int x)//dfs{ dfn[x]=++dfu;//记录搜索序号 push (x); low[x]=dfn[x]; int next=alist[x]; while(next) { int v=edge[next].v; if(ins[v]==true)//被搜过就不用再搜了 { low[x]=min(low[x],low[v]); } else if(ins[v]==false) { dfs(v); low[x]=min(low[x],low[v]); } next=edge[next].next; } if(dfn[x]==low[x])//如果搜回来了。 { while(low[stack[top]]==low[x]) { typ[stack[top]]=true; pop(); ans[x]++; } if(ans[x]>1) res++;//想要转圈的话必须要两个人及以上。 } return;}int n,m;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int n1,m1; scanf("%d%d",&n1,&m1);//不解释。 add(n1,m1); } for(int i=1;i<=n;i++) { if(typ[i]==1) continue;//要是在扫过的强连通分量里面直接过。 else dfs(i); } printf("%d",res); return 0;//程序拜拜}

 

转载于:https://www.cnblogs.com/cn-suqingnian/p/9179713.html

你可能感兴趣的文章
spfile
查看>>
Team Foundation Service更新:改善了导航和项目状态速查功能
查看>>
WordPress资源站点推荐
查看>>
Python性能鸡汤
查看>>
android Manifest.xml选项
查看>>
Cookie/Session机制具体解释
查看>>
ATMEGA16 IOport相关汇总
查看>>
有意思的cmd命令
查看>>
js正則表達式语法
查看>>
Git学习系列-Git基本概念
查看>>
c#多个程序集使用app.config 的解决办法
查看>>
Linux+Apache+PHP+MySQL服务器环境配置(CentOS篇)
查看>>
Linux下获取本机IP地址的代码
查看>>
(C#)调用Webservice,提示远程服务器返回错误(500)内部服务器错误
查看>>
flex布局
查看>>
python-----python的文件操作
查看>>
java Graphics2d消除锯齿,使字体平滑显示
查看>>
控件中添加的成员变量value和control的区别
查看>>
Spring Boot Docker 实战
查看>>
Div Vertical Menu ver3
查看>>