洛谷 P2863 [USACO06JAN]牛的舞会The Cow Prom
2024-08-28 11:14:16
题目大意:形成一个环的牛可以跳舞,几个环连在一起是个小组,求几个小组。
题解:tarjian缩点后,求缩的点包含的原来的点数大于1的个数。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10009
using namespace std; int n,m,sumedge,top,sumclr,tim,ans;
int Stack[maxn],instack[maxn],low[maxn],dfn[maxn],cnt[maxn],head[maxn]; struct Edge{
int x,y,nxt;
Edge(int x=,int y=,int nxt=):
x(x),y(y),nxt(nxt){}
}edge[maxn*]; void add(int x,int y){
edge[++sumedge]=Edge(x,y,head[x]);
head[x]=sumedge;
} void Tarjian(int x){
Stack[++top]=x;instack[x]=true;
low[x]=dfn[x]=++tim;
for(int i=head[x];i;i=edge[i].nxt){
int v=edge[i].y;
if(instack[v])low[x]=min(low[x],dfn[v]);
else if(!dfn[v]){
Tarjian(v);low[x]=min(low[x],low[v]);
}
}
if(low[x]==dfn[x]){
sumclr++;
while(Stack[top+]!=x){
instack[Stack[top]]=false;
cnt[sumclr]++;
top--;
}
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=;i<=n;i++)if(!dfn[i])Tarjian(i);
for(int i=;i<=sumclr;i++)if(cnt[i]>)ans++;
printf("%d\n",ans);
return ;
}
AC
最新文章
- @RequestMapping映射请求
- C#如何把List of Object转换成List of T具体类型
- LINUX 产生PPM 驱动例子
- PHP- 深入PHP、Redis连接
- ie6常见的兼容性
- hdu 3642 Get The Treasury(扫描线)
- 利用好CSS,实现Qt控件美化
- java基础之 第一步 :jdk安装配置
- 如何在Eclipse配置Tomcat服务器
- C3P0
- MongoDB和Redis区别
- ora-01440:要减小精度或标度,则要修改的列必须为空
- myeclipse将java项目转换成web项目,导出war包
- mysql 使用教程 入门
- 关于linux kernel slab内存管理的一点思考
- 关于js函数对象的理解
- jQuery UI全教程之一(dialog的使用教程)
- 【读书笔记】socket函数
- PAT 1057 数零壹 (20)(代码+思路)
- [美国代购] Nexus 6 与 Moto X 询价聊天记录整理