POJ2186 Popular Cows 【强连通分量】+【Kosaraju】+【Tarjan】

完美代码

于 2017-04-23 22:10:03 发布

阅读量4.9w

点赞数 1

谢绝转载-https://update.blog.csdn.net

本文链接：https://blog.csdn.net/update7/article/details/70551443

版权

编程. 同时被 2 个专栏收录

578 篇文章 ¥299.90 ¥399.90

订阅专栏

编程..

570 篇文章 ¥299.90 ¥399.90

订阅专栏

本文详细解析了POJ2186编程题的解题思路，重点介绍了强连通分量的概念，并通过Kosaraju算法和Tarjan算法进行实现。通过实例探讨如何在图论问题中应用这两种算法，帮助程序员提升图算法解决实际问题的能力。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

/*
Popular Cows （ POJ No.2186）
每头牛都想成为牛群中的红人。给定 N 头牛的牛群和 M 个有序对(A, B)。 (A, B)表示牛 A 认
为牛 B 是红人。该关系具有传递性，所以如果牛 A 认为牛 B 是红人，牛 B 认为牛 C 是红人，
那么牛 A 也认为牛 C 是红人。不过，给定的有序对中可能包含(A, B)和(B, C)，但不包含(A, C)。
求被其他所有牛认为是红人的牛的总数。
限制条件
 1 ≤ N ≤ 10000
 1 ≤ M ≤ 50000
 1 ≤ A, B ≤ N
 
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
次题为典型的求强连通分量的题目，将强连通分量缩点并得到DAG，
求的出度为0的强连通分量的点的个数就是答案
*/

//Kosaraju算法，异常巧妙
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10000+10,maxm=50000+10;
int n,m,scc;
int stack[maxn],top;
int head1[maxn],head2[maxn];
struct node{
	int to,next;
};
node edge1[maxm],edge2[maxm

了解本专栏