班长竞选

问题描述

大学班级选班长，N 个同学均可以发表意见，若意见为 A B，则表示 A 认为 B 合适。意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适。共有 M 条意见，求最高票数，并给出一份候选人名单，即所有得票最多的同学。

Input

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 ≤ n ≤ 5000, 0 < m ≤ 30000)，接下来有 M 行包含两个整数 A 和 B (A ≠ B) 表示 A 认为 B 合适。

Output

对于每组数据，第一行输出"Case x: "，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

Sample

Input: 
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2

Output: 
Case 1: 2
0 1
Case 2: 2
0 1 2

Limitation

Time limit		2000 ms
Memory limit	32768 kB

解题思路

这题题目短，题意清晰，输入输出简单明了，但实现起来挺复杂的。

强连通分量 (Strongly Connected Component, SCC)

有向图中，尽可能多的若干顶点组成的子图中，这些顶点都是相互可到达的，则这些顶点成为一个强连通分量。

如上图所示，有3个强连通分量，分别是{A, B, C}, {D, E, H}, {F, G}。

DFS序

前序：第一次到达点 x 的次序，用d[x]表示
后序：x 点遍历完成的次序，即回溯时间，用 f[x] 表示
逆后序：后序序列的逆序

以上图为例，用DFS遍历：

Edge	Current Node	Note
-	A	d[A] = 1
A → B	B	d[B] = 2
B → C	C	d[C] = 3
C → A	C	Reached
C → H	H	d[H] = 4
H → E	E	d[E] = 5
E → D	D	d[D] = 6
D → E	D	Reached
D → F	F	d[F] = 7
F → G	G	d[G] = 8
G → F	G	Reached
G遍历结束	G	f[G] = 1
F遍历结束	F	f[F] = 2
D遍历结束	D	f[D] = 3
E → G	E	Reached
E → H	E	Reached
E遍历结束	E	f[E] = 4
H遍历结束	H	f[H] = 5
C遍历结束	C	f[C] = 6
B → H	B	Reached
B遍历结束	B	f[B] = 7
A遍历结束	A	f[A] = 8

得到前序序列：{A, B, C, H, E, D, F, G}
后序序列：{G, F, D, E, H, C, B, A}
逆后序序列：{A, B, C, H, E, D, F, G}

Kosaraju Algorithm

Kosaraju算法用于找出图中所有的SCC。

以上图为例，DFS先求出原图的逆后序序列{A, B, C, H, E, D, F, G}，然后根据逆后序序列遍历反图(如下图)：

Step 1: 从A开始遍历，得到第一个SCC{A, C, B}

Step 2: 从H开始遍历，得到第二个SCC{H, E, D}

Step 3: 从F开始遍历，得到第三个SCC{F, G}

回到本题

投票选举，A认为B合适(A→B的有向边)，B认为C合适(B→C的有向边)，则A也认为C合适(传递性)。因此投票可能形成多个环路。

先求出共有多少个SCC，每一个SCC内，每个节点的票数 = 该SCC的节点数 - 1(除去自己)；
对于每个SCC，都可进行缩点，记作SCC[i]，其值为内节点的票数。
若SCC_i对SCC_j可达，且由 i 指向 j，则SCC[j] += SCC[i](传递性)。

票数最多的人，一定出现在出度为0的SCC中。

总共需要2次DFS求出强连通分量，1次DFS找出票数最高的即出度为0的强连通分量，然后再从这个SCC中找出票数最高的点，即答案。

本题综合性很强，很容易TLE或MLE。本来用的cin，后来用scanf才过……

源代码

#include <cstdio>
#include <memory>
#include <algorithm>
#include <cstring>
using namespace std;

struct node {
	int ele;
	node* next;
	node() { ele = -1; next = NULL; }
	node(int e) :ele(e) { next = NULL; }
};

class linkedList {
private:
	node* header;
	int size;
public:
	linkedList() { header = NULL; size = 0; }
	~linkedList() { clear(); }
	int getSize() { return size; }
	node* getHeader() { return header; }
	void add(int ele) {
		node* p = new node(ele);
		if (header == NULL)
			header = p;
		else {
			node* temp = header;
			node* temp2 = NULL;
			while (temp != NULL) {
				temp2 = temp;
				temp = temp->next;
			}
			temp2->next = p;
		}
		size++;
	}
	void clear() {
		node* temp = header;
		node* ttemp = NULL;
		while (temp != NULL) {
			ttemp = temp;
			temp = temp->next;
			ttemp = NULL;
		}
		header = NULL;
		delete temp;
		delete ttemp;
		delete header;
		size = 0;
	}
};

const int maxN = 5010;

class graph {
private:
	linkedList arr1[maxN];
	linkedList arr2[maxN];
	linkedList arr[maxN];
	int inDeg[maxN];
	bool reach1[maxN];
	int inv[maxN];
	int invCnt;
	int color[maxN];
	int scc[maxN];
	int sccCnt;
	int size;
	int ans[maxN];
	bool reach2[maxN];
	int s;
	int res[maxN];
	int count;
public:
	graph() { size = 0; }
	graph(int n) { size = n; initialize(); }
	~graph() {  }
	void initialize() {
		sccCnt = 0;
		s = 0;
		count = 0;
		invCnt = 0;
		for (int i = 0; i <= size; i++) {
			inDeg[i] = 0;
			reach1[i] = false;
			color[i] = 0;
			scc[i] = 0;
			ans[i] = 0;
			res[i] = 0;
		}
	}
	void add(int p1, int p2) {
		arr1[p1].add(p2);
	}
	void invertedAdd(int p1, int p2) {
		arr2[p1].add(p2);
	}
	void ADD(int p1, int p2) {
		arr[p1].add(p2);
		inDeg[p2]++;
	}
	void dfs1(int s) {
		reach1[s] = true;
		for (node* p = arr1[s].getHeader(); p != NULL; p = p->next) {
			int ele = p->ele;
			if (!reach1[ele])
				dfs1(ele);
		}
		inv[++invCnt] = s;
	}
	void dfs2(int s, int sccCnt) {
		color[s] = sccCnt;
		scc[sccCnt]++;
		for (node* p = arr2[s].getHeader(); p != NULL; p = p->next) {
			int ele = p->ele;
			if (!color[ele])
				dfs2(ele, sccCnt);
		}
	}
	void kosaraju() {
		for (int i = 1; i <= size; i++)
			if (!reach1[i])
				dfs1(i);

		for (int i = size; i >= 1; i--) {
			int x = inv[i];
			if (!color[x]) {
				sccCnt++;
				dfs2(x, sccCnt);
			}
		}
	}
	void dfs3(int x) {
		reach2[x] = true;
		for (node* p = arr[x].getHeader(); p != NULL; p = p->next) {
			int ele = p->ele;
			if (!reach2[ele]) {
				ans[s] += scc[ele];
				dfs3(ele);
			}
		}
	}
	int solve() {
		kosaraju();

		for (int i = 1; i <= size; i++) {
			for (node* p = arr2[i].getHeader(); p != NULL; p = p->next) {
				int ele = p->ele;
				if (color[i] == color[ele])
					continue;
				ADD(color[i], color[ele]);
			}
		}

		count = 0;
		for (int i = 1; i <= sccCnt; i++) {
			if (inDeg[i] == 0) {
				memset(reach2, false, maxN);
				ans[i] += (scc[i] - 1);
				s = i;
				dfs3(i);
				count = max(count, ans[i]);
			}
		}

		return count;
	}
	void solve2() {
		for (int i = 1; i <= sccCnt; i++)
			if (ans[i] == count)
				res[i] = 1;

		int pos = 0;
		for (int i = 1; i <= size; i++) {
			if (res[color[i]])
				if (pos == 0) {
					printf("%d", i - 1);
					pos++;
				}
				else
					printf(" %d", i - 1);
		}
		printf("\n");
	}
};

int main() {
	int t;
	scanf_s("%d", &t);
	for (int ii = 1; ii <= t; ii++) {
		int n, m;
		scanf_s("%d%d", &n, &m);
		graph G(n);
		for (int i = 0; i < m; i++) {
			int p1, p2;
			scanf_s("%d%d", &p1, &p2);
			G.add(p1 + 1, p2 + 1);
			G.invertedAdd(p2 + 1, p1 + 1);
		}
		int r = G.solve();
		printf("Case %d: %d\n", ii, r);
		G.solve2();
		G.~graph();
	}

	return 0;
}