UVa 11770 - Lighting Away

#include <memory.h>
#include <stdio.h>
#include <set>
#include <vector>
using namespace std;

#define MAXV 10001

/**
 * Strongly Connected Components in a a directed graph
 * from Stanford ACM ICPC notebook
 * Nodes indexes are 1-based. Define MAXV to be nubmer_of_nodes + 1
 */
class SCC {
	struct edge {
		int e, nxt;
	};
	int V;
	vector<vector<int> > edges, edges_reverse;

	int group_cnt, group_num[MAXV];
	bool visited[MAXV];
	int stk[MAXV];
	void fill_forward(int x) {
		visited[x] = true;
		for (int i = 0; i < edges[x].size(); i++)
			if (!visited[edges[x][i]])
				fill_forward(edges[x][i]);
		stk[++stk[0]] = x;
	}
	void fill_backward(int x) {
		visited[x] = false;
		group_num[x] = group_cnt;
		for (int i = 0; i < edges_reverse[x].size(); i++)
			if (visited[edges_reverse[x][i]])
				fill_backward(edges_reverse[x][i]);
	}
public:
	SCC(int number_of_nodes) {
		V = number_of_nodes;
		edges = vector<vector<int> >(V + 1);
		edges_reverse = vector<vector<int> >(V + 1);
		group_cnt = -1;
	}

	// add edge v1->v2
	void add_edge(int v1, int v2) {
		edges[v1].push_back(v2);
		edges_reverse[v2].push_back(v1);
	}

	void run() {
		int i;
		stk[0] = 0;
		memset(visited, false, sizeof(visited));
		for (i = 1; i <= V; i++)
			if (!visited[i])
				fill_forward(i);
		group_cnt = 0;
		for (i = stk[0]; i >= 1; i--)
			if (visited[stk[i]]) {
				group_cnt++;
				fill_backward(stk[i]);
			}
	}

	int getColorCount() {
		return group_cnt;
	}

	int getColorOfNode(int node) {
		return group_num[node];
	}

	vector<vector<int> > getEdges() {
		return edges;
	}

};

int main() {
	int cases;
	scanf("%d", &cases);
	for (int cas = 1; cas <= cases; cas++) {
		int number_of_nodes, number_of_edges;
		scanf("%d%d", &number_of_nodes, &number_of_edges);

		set<int> nodes_with_in_degree;

		SCC scc = SCC(number_of_nodes);
		for (int i = 0; i < number_of_edges; i++) {
			int v1, v2;
			scanf("%d%d", &v1, &v2);
			scc.add_edge(v1, v2);
			nodes_with_in_degree.insert(v2);
		}

		scc.run();

		bool parentless[MAXV];
		memset(parentless, true, sizeof(parentless));

		vector<vector<int> > edges = scc.getEdges();
		for (int i = 1; i <= number_of_nodes; i++) {
			for (vector<int>::iterator it = edges[i].begin(); it != edges[i].end(); it++) {
				int to_node = *it;
				if (scc.getColorOfNode(to_node) != scc.getColorOfNode(i))
					parentless[scc.getColorOfNode(to_node) - 1] = false;
			}
		}

		int parentless_nodes_in_SCC_DAG = 0;
		for (int i = 0; i < scc.getColorCount(); i++)
			if (parentless[i])
				parentless_nodes_in_SCC_DAG++;

		printf("Case %d: %d\n", cas, parentless_nodes_in_SCC_DAG);
	}
	return 0;
}