Logo Wy Online Judge

WyOJ

Paste!

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

struct Graph {
	int* value;
	unsigned n;
	std::vector<unsigned>* table;

	void add_edge(unsigned from, unsigned to) {
		table[from].push_back(to);
	}

	const std::vector<unsigned>& operator[](unsigned pos) const {
		return table[pos];
	}

	Graph(unsigned v_count)
		: value(new int[v_count]()), n(v_count), table(new std::vector<unsigned>[v_count]) {
	}
};

class Tarjan {
	std::vector<unsigned> stack;
	bool* visit;
	unsigned dfs_index;
	unsigned *low, *dfi;
	const Graph& G;

public:
	unsigned scc_n, *scc_index;

private:
	void dfs(unsigned now) {
		low[now] = dfi[now] = ++dfs_index;
		stack.push_back(now);
		visit[now] = true;
		for (auto i: G[now])
		{
			if (!dfi[i])
			{
				dfs(i);
				low[now] = std::min(low[i], low[now]);
			}
			else if (visit[i])
				low[now] = std::min(dfi[i], low[now]);
		}
		if (low[now] == dfi[now])
		{
			unsigned top;
			do
			{
				scc_index[stack.back()] = scc_n;
				visit[stack.back()] = false;
				top = stack.back();
				stack.pop_back();
			} while (!stack.empty() && top != now);
			++scc_n;
		}
	}

public:
	void operator()() {
		std::fill_n(visit, G.n, false);
		std::fill_n(dfi, G.n, 0u);
		dfs_index = scc_n = 0;
		for (int i = 0; i < G.n; i++)
			if (!dfi[i])
				dfs(i);
	}

	Graph DAG() {
		operator()();
		Graph res(scc_n);
		for (int i = 0; i < G.n; i++)
		{
			unsigned u = scc_index[i];
			res.value[u] += G.value[i];
			for (auto j: G[i])
			{
				unsigned v = scc_index[j];
				if (u != v)
					res.add_edge(u, v);
			}
		}

		return res;
	}

	Tarjan(const Graph& graph)
		: visit(new bool[graph.n]), dfs_index(0), low(new unsigned[graph.n]),
		  dfi(new unsigned[graph.n]), G(graph), scc_n(0), scc_index(new unsigned[graph.n]) {
	}
};

int main() {
	using namespace std;
	int n;
	cin >> n;
	Graph G(n);
	for (int i = 0; i < n; i++)
	{
		int to;
		cin >> to;
		while (to)
		{
			G.table[i].push_back(to - 1);
			cin >> to;
		}
	}
	G = Tarjan(G).DAG();
	auto in_deg = new int[G.n](), ou_deg = new int[G.n]();
	for (int i = 0; i < G.n; i++)
		for (auto j: G[i])
		{
			++in_deg[j];
			++ou_deg[i];
		}
	int cnti = 0, cnto = 0;
	for (int i = 0; i < G.n; i++)
	{
		if (!in_deg[i])
			++cnti;
		if (!ou_deg[i])
			++cnto;
	}
	if (G.n == 1)
		cout << 1 << endl << 0 << endl;
	else
		cout << cnti << endl << max(cnti, cnto) << endl;
	delete[] in_deg;
	delete[] ou_deg;
	return 0;
}