传送门

题目大意:形成一个环的牛可以跳舞,几个环连在一起是个小组,求几个小组。

题解: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

最新文章

  1. @RequestMapping映射请求
  2. C#如何把List of Object转换成List of T具体类型
  3. LINUX 产生PPM 驱动例子
  4. PHP- 深入PHP、Redis连接
  5. ie6常见的兼容性
  6. hdu 3642 Get The Treasury(扫描线)
  7. 利用好CSS,实现Qt控件美化
  8. java基础之 第一步 :jdk安装配置
  9. 如何在Eclipse配置Tomcat服务器
  10. C3P0
  11. MongoDB和Redis区别
  12. ora-01440:要减小精度或标度,则要修改的列必须为空
  13. myeclipse将java项目转换成web项目,导出war包
  14. mysql 使用教程 入门
  15. 关于linux kernel slab内存管理的一点思考
  16. 关于js函数对象的理解
  17. jQuery UI全教程之一(dialog的使用教程)
  18. 【读书笔记】socket函数
  19. PAT 1057 数零壹 (20)(代码+思路)
  20. [美国代购] Nexus 6 与 Moto X 询价聊天记录整理

热门文章

  1. jQuery/CSS3 图片边框线条变换动画
  2. JavaWeb Listener
  3. Python 函数定义和使用
  4. sem学习
  5. 移动端给img元素添加content: &quot;&quot;;
  6. spring: @RequestMapping注解
  7. Android调用系统相机拍照保存照片很小解决方案
  8. python函数式编程之高阶函数学习
  9. MyEclipse安装git插件
  10. python运行httpserver