专栏首页wym[USACO06JAN]牛的舞会 Tarjan模版

[USACO06JAN]牛的舞会 Tarjan模版

[USACO06JAN]牛的舞会

只要找强联通分量大于一的个数就行

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
struct E{int v,nxt;};
E edge[N];
int dfn[N],low[N],cnt,visnum,num[N],belong[N],head[N];
int n,m,vis[N];
stack<int> q;
void tarjan(int u){
	dfn[u] = low[u] = ++visnum;
	vis[u] = 1;
	q.push(u);
	for(int v,i=head[u];i;i=edge[i].nxt){
		v = edge[i].v;
		if(!vis[v]){
			tarjin(v);
			low[u] = min(low[u],low[v]);
		}else low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++cnt;
		int v;
		do{
			v = q.top();q.pop();
			belong[v] = cnt;
			num[cnt]++;
			vis[v] = 0;
		}while(u!=v);//回溯 
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		edge[i].v = v; edge[i].nxt = head[u]; head[u] = i;
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjin(i);
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		if(num[i]>1)ans++;
	}printf("%d\n",ans);
	return 0;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • 种树 差分约束|贪心

    每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。

    用户2965768
  • 2039. 树的统计

    输入文件:counttree.in   输出文件:counttree.out 简单对比 时间限制:1 s   内存限制:128 MB 【题目描述】 关于...

    attack
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf

扫码关注云+社区

领取腾讯云代金券