poj2186

maksyuki 发表于 oj 分类，标签: 图论-有向图强连通分量

22 1月 2016

Popular Cows

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.

Input

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

Output

* Line 1: A single integer that is the number of cows who are considered popular by every other cow.

Sample Input

3 3

1 2

2 1

2 3

Sample Output

Hint

Cow 3 is the only cow of high popularity.

Source

USACO 2003 Fall

题目类型：有向图重连通分量(Tarjan)+缩点

算法分析：由于仰慕关系可以传递，则若一个强连通分量Q中的某个点被外部点A所仰慕，则Q中所有点都会被A仰慕。同样，若Q中的某个点仰慕某个外部点B，则Q中所有点都会仰慕B。所以可以缩点，找新构成的图中出度为0的点(注意这个点是可能是缩点！！！)，若出度为0的点的个数不为1，则输出0。否则输出当前缩点中点的个数

/*************************************************
Author        :supermaker
Created Time  :2016/1/22 21:06:14
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 10000 + 66;

int dfn[maxn], low[maxn], belong[maxn], outdeg[maxn], num[maxn];
int n, m, id, tot;
bool instack[maxn];
vector <int> g[maxn];
stack <int> sta;

void dfs (int u)
{
	dfn[u] = low[u] = ++id;
	instack[u] = true;
	sta.push (u);
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i];
		if (!dfn[v])
		{
			dfs (v);
			low[u] = min (low[u], low[v]);
		}
		else if (instack[v])
			low[u] = min (low[u], dfn[v]);
	}
	if (low[u] == dfn[u])
	{
		tot++;
		int tt;
		do
		{
			tt = sta.top (); sta.pop ();
			instack[tt] = false;
			belong[tt] = tot;
			num[tot]++;
		} while (!sta.empty () && tt != u);
	}
}

void SS ()
{
	memset (dfn, 0, sizeof (dfn));
	memset (low, 0, sizeof (low));
	memset (num, 0, sizeof (num));
	memset (instack, false, sizeof (instack));
	tot = id = 0;
	while (!sta.empty ()) sta.pop ();
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs (i);
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		for (int i = 0; i < maxn; i++)
			g[i].clear ();
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			g[u].push_back (v);
		}
		SS ();
		
		memset (outdeg, 0, sizeof (outdeg));
		for (int u = 1; u <= n; u++)
			for (int i = 0; i < g[u].size (); i++)
			{
				int v = g[u][i];
				if (belong[u] != belong[v])
					outdeg[belong[u]]++;
			}
		int res = 0, pos = 1;
		for (int i = 1; i <= tot; i++)
			if (!outdeg[i])
				pos = i, res++;

		if (res == 1) printf ("%d\n", num[pos]);
		else puts ("0");
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

/*************************************************

Author :supermaker

Created Time :2016/1/22 21:06:14

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 10000 + 66;

int dfn[maxn], low[maxn], belong[maxn], outdeg[maxn], num[maxn];

int n, m, id, tot;

bool instack[maxn];

vector <int> g[maxn];

stack <int> sta;

void dfs (int u)

{

dfn[u] = low[u] = ++id;

instack[u] = true;

sta.push (u);

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (!dfn[v])

{

dfs (v);

low[u] = min (low[u], low[v]);

}

else if (instack[v])

low[u] = min (low[u], dfn[v]);

}

if (low[u] == dfn[u])

{

tot++;

int tt;

{

tt = sta.top (); sta.pop ();

instack[tt] = false;

belong[tt] = tot;

num[tot]++;

} while (!sta.empty () && tt != u);

}

void SS ()

{

memset (dfn, 0, sizeof (dfn));

memset (low, 0, sizeof (low));

memset (num, 0, sizeof (num));

memset (instack, false, sizeof (instack));

tot = id = 0;

while (!sta.empty ()) sta.pop ();

for (int i = 1; i <= n; i++)

if (!dfn[i])

dfs (i);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &m) != EOF)

{

for (int i = 0; i < maxn; i++)

g[i].clear ();

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

g[u].push_back (v);

}

SS ();

memset (outdeg, 0, sizeof (outdeg));

for (int u = 1; u <= n; u++)

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (belong[u] != belong[v])

outdeg[belong[u]]++;

}

int res = 0, pos = 1;

for (int i = 1; i <= tot; i++)

if (!outdeg[i])

pos = i, res++;

if (res == 1) printf ("%d\n", num[pos]);

else puts ("0");

}

return 0;

}

poj2762

poj2553

超客的水墨烟雨

poj2186

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30