题意:一群牛被有向的绳子拴起来,如果有一些牛(>=2)的绳子是同向的,他们就能跳跃。求能够跳跃的组数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf =0x7f7f7f7f;
const double pi=acos(-1);
const int maxn=10000; vector<int> G[maxn+10];
int n,m,deg[maxn+10],pre[maxn+10],dfs_clock,scc_cnt,sccno[maxn+10],lowlink[maxn+10];
stack<int> S; void tarjan(int u)
{
pre[u]=lowlink[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
tarjan(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(!sccno[v])
lowlink[u]=min(lowlink[u],pre[v]);
} if(lowlink[u]==pre[u])
{
scc_cnt++;
while(1)
{
int x=S.top();S.pop();
sccno[x]=scc_cnt;
deg[scc_cnt]++;
if(x==u) break;
}
}
} void find_scc()
{
MM(pre,0);MM(sccno,0);
scc_cnt=dfs_clock=0;
for(int i=1;i<=n;i++)
if(!pre[i])
tarjan(i);
} int main()
{
while(~scanf("%d %d",&n,&m))
{
for(int i=1;i<=n;i++)
G[i].clear(); for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
} MM(deg,0);
find_scc();
int ans=0;
for(int i=1;i<=scc_cnt;i++)
if(deg[i]>=2) ans++;
printf("%d\n",ans);
}
return 0;
}

  分析:牛能一起跳舞那么他们的绳子朝向就一定是一致的,也就是形成了一个环,即一个强连通分量,

所以只要统计好整个图中元素个数>=2的强连通分量个数就好

最新文章

  1. javaweb学习总结(二十六)——jsp简单标签标签库开发(二)
  2. mongodb 基本指令学习
  3. JS之tagNaem和nodeName
  4. Java 理论和实践: 了解泛型
  5. json2使用方法
  6. Apache Wamp WampServer 配置多端口 多站点 虚拟目录
  7. C#日期格式精确到毫秒以及上下午
  8. MessageQueue
  9. cocos2dx中的层CCLayer
  10. JS 某一区域内所有CheckBox全选和取消全选(.net)
  11. archlinux系统安装博通B43XX系列无线网卡驱动
  12. Count Color 线段树
  13. 适合Linux新手的发行版有哪些?
  14. Angular4.0用命令行创建组件服务出错
  15. 软件性能测试技术树(二)----Linux服务器性能
  16. sql中的等于和不等于, &#39;=&#39; ,&#39;!=&#39;,&#39;&lt;&gt;&#39;,&#39;is null&#39;....
  17. Vue(九):样式绑定v-bind示例
  18. 为linux dns (bind named)服务器配置 单独的笔记
  19. linux 打开一个文件现swap文件
  20. Web安全测试-WebScarab

热门文章

  1. DVWA、 DSVM 环境搭建简述
  2. IM学习目录
  3. mknod创建设备(加载新的设备驱动时候,通常会用到此命令)
  4. Git+码云安装
  5. python中常见的一些错误异常类型
  6. CS起源:实现狙击子弹加速
  7. java延时队列
  8. 剑指offer-把数组排成最小的数-数组-python
  9. elementui 之el-pagination爬坑,属性pager-count的设定
  10. RabbitMQ从安装到使用