Hawk-and-Chicken

Problem Description

Kids in kindergarten enjoy playing a game called Hawk-and-Chicken. But there always exists a big problem: every kid in this game want to play the role of Hawk. 
So the teacher came up with an idea: Vote. Every child have some nice handkerchiefs, and if he/she think someone is suitable for the role of Hawk, he/she gives a handkerchief to this kid, which means this kid who is given the handkerchief win the support. Note the support can be transmitted. Kids who get the most supports win in the vote and able to play the role of Hawk.(A note:if A can win
support from B(A != B) A can win only one support from B in any case the number of the supports transmitted from B to A are many. And A can't win the support from himself in any case.
If two or more kids own the same number of support from others, we treat all of them as winner.
Here's a sample: 3 kids A, B and C, A gives a handkerchief to B, B gives a handkerchief to C, so C wins 2 supports and he is choosen to be the Hawk.

Input

There are several test cases. First is a integer T(T <= 50), means the number of test cases.
Each test case start with two integer n, m in a line (2 <= n <= 5000, 0 <m <= 30000). n means there are n children(numbered from 0 to n - 1). Each of the following m lines contains two integers A and B(A != B) denoting that the child numbered A give a handkerchief to B.

Output

For each test case, the output should first contain one line with "Case x:", here x means the case number start from 1. Followed by one number which is the total supports the winner(s) get. 
Then follow a line contain all the Hawks' number. The numbers must be listed in increasing order and separated by single spaces.

Sample Input

2

4 3
3 2
2 0
2 1

3 3
1 0
2 1
0 2
 

Sample Output

Case 1: 2

0 1

Case 2: 2

0 1 2

题目分析

题意：小朋友们玩老鹰捉小鸡的游戏，但是每个孩子都想扮演老鹰，于是老师决定通过投票决定谁当老鹰，自己不可以给自己投票，投票还具有传递性，也就是如果A投了B，同时B投了C，那么相当于A投了C。求出最大投票数，同时我们需要找到投票数最多的孩子，如果孩子不唯一，输出所有投票数最大的孩子。

思路：我们知道强连通分量中的点可以相互到达，那么同一个强连通分量中的孩子是相互投票的（传递性），那么我们将强连通分量缩成点，以强连通分量之间的边构建出DAG图（有向无环图），我们知道DAG图中的点是线性关系的，我们深搜的复杂度就是O(n)，因此我们只需要找到出度为0的点，反向深搜，统计经过的点的总数，最后我们比较所有的出度为0的点深搜得到的投票数，求出投票数最大的那些人，输出最大投票数和拥有最大投票数的人即可。

（第一次写的的时候用vector保存路径，然后出现了稀有的MLE，回头一想，这里不需要记录路径吧！记录一下深搜过程中访问过的点的数量即可。代码写的比较复杂，请见谅。）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip> 
#define bug cout << "**********" << endl
#define out cout<<"---------------"<<endl
#define show(x, y) "["<<x<<","<<y<<"] "
//#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e8;
const int Max = 3e4 + 10;
const int Max2 = 5e3 + 10;

struct Edge {
	int to, next;
} edge[Max], reverse_edge[Max];

int n, m;
int head[Max2], tot;
int reverse_head[Max2], reverse_tot;			//反向建图
int dfn[Max2], low[Max2], time_clock;
int node[Max2], ans;							//记录每个点所属强连通分量的编号
vector<int> block[Max2];						//记录每一个连通分量具体的学生编号
int sum[Max2];									//记录每一个强连通分量收到的支持+自身的人数
bool vis[Max];									//记录是否访问，辅助计数
int out_d[Max];									//记录出度
vector<int>student;
int line[Max2], now;

void init() {
	memset(head, -1, sizeof(head));
	tot = 0;
	memset(reverse_head, -1, sizeof(reverse_head));
	reverse_tot = 0;

	memset(dfn, -1, sizeof(dfn));
	time_clock = 0;

	memset(node, -1, sizeof(node));
	for (int i = 1;i <= ans; i++)
		block[i].clear();
	ans = 0;

	memset(sum, -1, sizeof(sum));

	memset(out_d, 0, sizeof(out_d));

	student.clear();

	now = 0;
}


void add(int u, int v) {
	edge[tot].to = v;
	edge[tot].next = head[u];
	head[u] = tot++;							//正向建图

	reverse_edge[reverse_tot].to = u;
	reverse_edge[reverse_tot].next = reverse_head[v];
	reverse_head[v] = reverse_tot++;			//反向建图
}


void tarjan(int u) {
	dfn[u] = low[u] = ++time_clock;
	line[++now] = u;

	for (int i = head[u]; i != -1; i = edge[i].next) {
		int v = edge[i].to;
		if (dfn[v] == -1) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (node[v] == -1) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {						//形成强连通分量
		ans++;
		while (line[now] != u) {
			block[ans].push_back(line[now]);	//记录强连通分量中的点，方便输出其中的点
			node[line[now--]] = ans;			//记录每个点所属的强连通分量
		}
		block[ans].push_back(line[now]);
		node[line[now--]] = ans;
	}
}

void dfs(int now, int fa)						//反向深搜
{
	sum[now] = block[now].size();				//先计算自身的，这里假装所有人给自己投了票，最后减去自己即可
	vis[now] = true;

	for (int u = 0;u < block[now].size(); u++)	//从当前强连通分量向其他地方转移
	{
		for (int i = reverse_head[block[now][u]]; i != -1; i = reverse_edge[i].next)
		{
			int v = reverse_edge[i].to;
			if (now == node[v] || node[v] == fa || vis[node[v]])
				continue;

			if (!vis[node[v]])					//没有访问过的强连通分量，避免重复访问
			{
				dfs(node[v], now);				//向下深搜
				sum[now] += sum[node[v]];		//加上刚刚访问的强连通分量的sum
			}
		}
	}
}


int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	int kCase = 0;
	while (t--) {
		scanf("%d%d", &n, &m);
		init();
		for (int i = 1, u, v; i <= m; i++) {
			scanf("%d%d", &u, &v);
			add(u, v);
		}
		for (int i = 0; i < n; i++) if (dfn[i] == -1) tarjan(i);

		for (int u = 0;u < n; u++)
		{
			for (int i = head[u]; i != -1; i = edge[i].next)
			{
				int v = edge[i].to;
				if (node[u] != node[v])		//统计每一个强连通分量的出度
				{
					out_d[node[u]]++;
				}
			}
		}

		for (int i = 1; i <= ans; i++)
		{
			if (out_d[i] == 0)				//出度为0的点的投票数肯定大于出度不为0的
			{
				memset(vis, 0, sizeof(vis));//这个要打破上一次的影响
				dfs(i, -1);
			}
		}
		int max_num = 0;
		for (int i = 1;i <= ans;i++)
		{
			if(out_d[i] == 0)
			{
				if (max_num < sum[i])		//出现了投票数更大的
				{
					max_num = sum[i];
					student = block[i];
				}
				else if (max_num == sum[i])	//同为最大投票数
				{
					student.insert(student.end(), block[i].begin(), block[i].end());
				}
			}
		}
		sort(student.begin(), student.end());
		printf("Case %d: %dn", ++kCase, max_num - 1);	//因为算了自己，这里的最大投票数要减一
		for (int i = 0;i < student.size() - 1;i++)
		{
			printf("%d ", student[i]);
		}
		printf("%dn", student[student.size() - 1]);
	}
	return 0;
}

最后

以上就是繁荣狗为你收集整理的POJ 3639 Hawk-and-Chicken （tarjan缩点+反向dfs）                            Hawk-and-Chicken的全部内容，希望文章能够帮你解决POJ 3639 Hawk-and-Chicken （tarjan缩点+反向dfs）                            Hawk-and-Chicken所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。