题解 P2863 【[USACO06JAN]牛的舞会The Cow Prom】
2024-09-03 12:09:31
赤裸裸的板子,就加一个特判就行。直接上代码
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
bool ins[];//记录入没入栈。
bool typ[];//特判*1,是强连通分量就直接过了。
int top;int ans[];
int stack[];//手写栈。
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[];
int cnt;int alist[];
void add(int u,int v)//继续手写结构体。
{
edge[++cnt].v=v;
edge[cnt].next=alist[u];
alist[u]=cnt;
}
int dfn[];int dfu;//dfn作为x的入栈序号。
int low[];int res=;
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]>) res++;//想要转圈的话必须要两个人及以上。
}
return;
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int n1,m1;
scanf("%d%d",&n1,&m1);//不解释。
add(n1,m1);
}
for(int i=;i<=n;i++)
{
if(typ[i]==) continue;//要是在扫过的强连通分量里面直接过。
else dfs(i);
}
printf("%d",res);
return ;//程序拜拜
}
最新文章
- [入门级] visual studio 2010 mvc4开发,用ibatis作为数据库访问媒介(一)
- 理解 OpenStack Swift (1):OpenStack + 三节点Swift 集群+ HAProxy + UCARP 安装和配置
- 【HDU 5858】Hard problem
- 留只脚印(DP)
- hdu1166 线段树
- delphi关闭程序Close,application.Terminate与halt区别
- 在windows下添加php的Imagick扩展
- Git - Tutorial [Lars Vogel]
- [Windows]VS2010如何以管理员权限启动?(转)
- Glog
- jQuery事件函数bind,live,delegate的区别
- BZOJ 3713: [PA2014]Iloczyn( 枚举 )
- 高并发环境下全局id生成策略
- L2-006 树的遍历 (25 分)
- Gradle目录结构详解
- hadoop安装笔记
- plsql界面/command界面
- percona mysql5.7关闭审计功能方法
- unshift() 方法将一个或多个元素添加到数组的开头,并返回新数组的长度
- <;项目管理的决策力>;总结梳理