URAL 1198. Jobbery

Author: 2015-08-21

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1198

1198. Jobbery

Time limit: 2.0 second
Memory limit: 64 MB
Hard times came for Martian senate. Even this pride of Martian democracy can not oppose the almighty jobbery. Let’s consider the procedure of typical decision making. A member of Martian senate, who needs a certain law, submits it to senate. To improve his chances that law is accepted, he makes a phone call to each of senate members on whom he has the goods in his safe. Then he kindly suggests to those senators to support the new law. Moreover, to avoid occasional rejection of this important law, he asks each of them to make the same procedure with their safes. And each of them having no choice makes a similar range of phone calls to those on whome, in turn, he has the goods. If every senator supports the new law the president has nothing to do but to approve it. Otherwise he can reject it and send back to senate for law improvements.
It is evident, that just elected president Honestman dislikes such situation. So he starts to struggle against the jobbery. And first of all he wants to put to jail the most dangerous senate members. And definitely, if senator is able to make even the harmful law approved, he is a dangerous one. So secret service of Martian president has already checked safes of each senate member, and found out on whom each of them has the goods. Martian president knows about your achievements in programming and he asks you personally for a help.

Input

The first line of input contains single integer N — the number of senate members (1 ≤ N ≤ 2000). Each senate member is uniquely identified with a number from 1 to N. Each of subsequent N lines contains information about senate members. The i-th line contains list of senate members (given by numeric identifiers) on whome he has the goods. List is terminated by number 0.

Output

Print the list of identifiers of all dangerous senate members in a single line. The numbers in the list must be present in increasing order. The list must be terminated by number 0.

Sample

input output 
5
3 2 0
0
4 5 0
1 5 0
2 0
 
1 3 4 0
Problem Author: Nikita Rybak

2. 思路

题目大意是说一些参议员握有其他参议员的把柄，可以进行胁迫其他参议员，这种关系可以传递，如A有B的把柄，B有C的把柄，则A可以直接胁迫B，B可以直接胁迫C，A也可以通过B来胁迫C。求“most dangerous senate members”。题目对“dangerous”的判定标准描述的不是很清楚，其实是求是否有一组参议员，他们之间任意两人之间都存在胁迫关系。

求有向图中是否只存在一个入度为0的强连通分量，下面的代码中使用Tarjan算法求解。

3. 代码

#include <stdio.h>

#define MAX_N 2001

typedef short Connection[MAX_N][MAX_N];

void solveE3d_Jobbery();
short inputConnection(Connection connection);
void tarjan(int n);
void strongConnect(int v);

int main() {
	solveE3d_Jobbery();
	return 0;
}

Connection connection;
int sccIdLut[MAX_N], sccInDegree[MAX_N], sccIdCnt = 0;
void solveE3d_Jobbery() {
	short n = inputConnection(connection);

	tarjan(n);

	for (int i = 1; i <= n; ++i) {
		int sccId = sccIdLut[i];
		for (int j = 0; connection[i][j] != 0; ++j) {
			if (sccIdLut[i] != sccIdLut[connection[i][j]])
				++sccInDegree[sccIdLut[connection[i][j]]];
		}
	}

	short zeroInDegId, zeroInDegCnt = 0;
	for (int i = 1; i <= sccIdCnt; ++i) {
		if (sccInDegree[i] == 0) {
			zeroInDegId = i;
			++zeroInDegCnt;
		}
	}

	if (zeroInDegCnt != 1) {
		printf("0\n");
		return;
	}

	for (int i = 1; i <= n; ++i) {
		if (sccIdLut[i] == zeroInDegId) {
			printf("%d ", i);
		}
	}
	printf("0\n");

}

short inputConnection(Connection connection) {
	int n;
	scanf("%d", &n);

	int senateId, cnt = 0;
	for (int i = 1; i <= n;) {
		scanf("%d", &senateId);
		connection[i][cnt++] = (short)senateId;
		if (senateId == 0) {
			++i;
			cnt = 0;
		}
	}

	return n;
}

int lowLink[MAX_N], stack[MAX_N], index[MAX_N], indexCnt = 0, top = 0;
bool onStack[MAX_N];
void tarjan(int n) {
	for (int i = 1; i <= n; ++i) {
		onStack[i] = false;
		index[i] = 0;
		sccIdLut[i] = 0;
	}

	indexCnt = 0;
	top = 0;

	for (int v = 1; v <= n; ++v) {
		if (index[v] == 0) {
			strongConnect(v);
		}
	}
}

void strongConnect(int v) {
	index[v] = lowLink[v] = ++indexCnt;
	stack[++top] = v;
	onStack[v] = true;

	for (int i = 0; connection[v][i] != 0; ++i) {
		int w = connection[v][i];
		if (index[w] == 0) {
			strongConnect(w);
			lowLink[v] = lowLink[v] < lowLink[w] ? lowLink[v] : lowLink[w];
		} else if (onStack[w]) {
			lowLink[v] = lowLink[v] < index[w] ? lowLink[v] : index[w];
		}
	}

	if (lowLink[v] == index[v]) {
		++sccIdCnt;
		int w;
		do {
			w = stack[top--];
			onStack[w] = false;
			sccIdLut[w] = sccIdCnt;
		} while (v != w);
	}
}