Cod sursa(job #1646958)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 10 martie 2016 18:22:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

void dfs(const int cur, const vector<vector<int> >& graf, vector<int>& st, vector<bool>& e_viz){
	e_viz[cur] = true;
	for(int i = 0; i < graf[cur].size(); ++i){
		const int next = graf[cur][i];
		if(!e_viz[next]){
			dfs(next, graf, st, e_viz); } }
	st.push_back(cur); }


void first_step(const int n, const vector<vector<int> >& graf, vector<int>& st){
	vector<bool> e_viz(n, false);

	for(int i = 0; i < n; ++i){
		if(!e_viz[i]){
			dfs(i, graf, st, e_viz); } } }

void second_step(const int n, const vector<vector<int> >& graf_t, vector<int>& st,
		vector<vector<int> >& rez){
	vector<bool> e_viz(n, false);

	while(!st.empty()){
		const int cur = st.back();
		st.pop_back();
		if(!e_viz[cur]){
			rez.push_back(vector<int>(0, 0));
			dfs(cur, graf_t, rez.back(), e_viz); } } }

int main(){
	ifstream f("ctc.in");
	ofstream g("ctc.out");

	int n, m;
	f >> n >> m;

	vector<vector<int> > graf(n), graf_t(n);

	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		--a, --b;
		graf[a].push_back(b);
		graf_t[b].push_back(a); }

	vector<int> st;

	first_step(n, graf, st);

	vector<vector<int> > rez;

	second_step(n, graf_t, st, rez);

	g << rez.size() << endl;

	for(int i = 0; i < rez.size(); ++i){
		sort(rez[i].begin(), rez[i].end());
		for(int j = 0; j < rez[i].size(); ++j){
			g << rez[i][j]+1 << ' '; }
		g << '\n'; }

	return 0; }