Computing strongly connected components

scc.cpp

#include <bits/stdc++.h>

#define S(x) scanf("%d", &x)
#define For(i, x, y) for(int i = x; i < y; ++i)
#define Fill(a, x) memset(a, x, sizeof(a))

void dout() { printf("\n"); }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
  #ifndef ONLINE_JUDGE
  	std::cout << H << ' ';
  	dout(T...);
  #endif
}

using namespace std;

struct Input {
	double beg;
	int n;
	vector < vector<int> > g, gr;
	vector<char> used;
	vector<int> order, component;
	vector<int> components;
	
	bool read () {
		#ifndef ONLINE_JUDGE 
			beg = clock();
		#endif

		ifstream ifs("SCC.txt");
		string line;
 
		while (getline(ifs, line)) {
			if (ifs.eof() || line.size() == 0) break;
			
		    stringstream ss(line);
		    
		    int a, b;
		    ss >> a >> b; --a; --b;

		    if (g.size() < max(a+1, b+1)) {g.resize(max(a+1, b+1)); gr.resize(max(a+1, b+1));}
		    
		    g[a].push_back(b);
		    gr[b].push_back(a);
 		}
 		ifs.close();

 		n = g.size();
	}

	void init (const Input &input) {
		*this = input;
	}
};

struct Output: Input {
	string res;
	
	void write () {
		For(i, components.size(), 5) components.push_back(0);

		sort(components.begin(), components.end());
		reverse(components.begin(),components.end());

		For(i, 0, 5) printf("%d ", components[i]);

		#ifndef ONLINE_JUDGE
			double end=clock();
			printf("\n*** Total time = %.3lf ***\n",(end-beg)/CLOCKS_PER_SEC);
		#endif
	}
	
	virtual void solve () {}
	
	virtual void clear () {
		*this = Output();
	}
};

struct Solution: Output {
	void dfs1 (int v) {
		used[v] = true;
		for (size_t i=0; i<g[v].size(); ++i)
			if (!used[ g[v][i] ])
				dfs1 (g[v][i]);
		order.push_back (v);
	}
	 
	void dfs2 (int v) {
		used[v] = true;
		component.push_back(v);
		for (size_t i=0; i<gr[v].size(); ++i)
			if (!used[ gr[v][i] ])
				dfs2 (gr[v][i]);
	}

	void solve () {
		used.assign (n, false);
		for (int i=0; i<n; ++i)
			if (!used[i])
				dfs1 (i);
		used.assign (n, false);
		for (int i=0; i<n; ++i) {
			int v = order[n-1-i];
			if (!used[v]) {
				dfs2 (v);
				
				components.push_back(component.size());
				
				component.clear();
			}
		}
	}
	
	void clear () {
		*this = Solution();
	}
};

Solution _sol;

int main () {
	_sol.read();
	_sol.solve();
	_sol.write();
	
	return 0;
}

SCC.txt

1 4
2 8
3 6
4 7
5 2
6 9
7 1
8 5
8 6
9 7
9 3