R0013. 「T3」街道赛跑 Solution

返回题目

题目分析：

核心思想：有向图 Dfs遍历。

首先我们要存图。虽然邻接表的确功能和优点很强大，但是这道题目50个点，100条边还是邻接矩阵好写多了。在练习邻接表的时候别忘记练习下邻接矩阵。

这道题目分两问，第一问其实很好做，怎么去搜索“不可避免的点”呢，只要把从这个点出发的所有边都标记为不通，然后再去看是不是所有点都被遍历了就可以了。

第二问的答案一定都包含在第一问的答案里面。所以我们可以直接搜索第一问的答案。从第一问的答案的那个点开始遍历，看那个点之前的点有没有被遍历到就可以了。

$\mathrm{Code:}$

#pragma(3,"Ofast")
#include <iostream>
using namespace std;
bool m[51][51], vis[51], vis2[51];
int a[51], a2[51], p1, p2, p3 = 0;
#define int register int

bool dfs1(int x) {
	if (vis[x]) {
		return false;
	}
	if (x == p3) {
		return true;
	}
	vis[x] = true;
	for (int i = 0; i <= p3; i++) {
		if (m[x][i] ) {
			if (dfs1(i)) {
				return true;
			}
		}
	}
	return false;
}

bool dfs2(int x) {
	if (vis[x]) {
		return true;
	}
	if (vis2[x]) {
		return false;
	}
	vis2[x] = true;
	for (int i = 0; i <= p3; i++) {
		if (m[x][i]) {
			if (dfs2(i)) {
				return true;
			}
		}
	}
	return false;
}
#undef int

int main() {
#define int register int
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	while (true) {
		int t;
		cin >> t;
		if (t == -1) {
			break;
		}
		if (t == -2) {
			p3++;
		} else {
			m[p3][t] = true;
		}
	}
	p3--;
	for (int i = 1; i <= p3 - 1; i++) {
		for (int j = 0; j <= p3; j++) {
			vis[j] = false;
		}
		vis[i] = true;
		for (int j = 0; j <= p3; j++) {
			vis2[j] = false;
		}
		if (!dfs1(0)) {
			a[p1++] = i;
			vis[i] = false;
			if (!dfs2(i)) {
				a2[p2++] = i;
			}
		}
	}
	cout << p1;
	for (int i = 0; i <= p1 - 1; i++) {
		cout << " " << a[i];
	}
	cout << endl << p2;
	for (int i = 0; i <= p2 - 1; i++) {
		cout << " " << a2[i];
	}
	return 0;
}

我写题解的怎么可能给你 $\mathrm{WA}$ 代码蛋子？这代码绝对保 $\mathrm{AC}$。