Cod sursa(job #2299273)

Utilizator VadimCCurca Vadim VadimC Data 9 decembrie 2018 11:11:07
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define NMax 100010

int n, m;
vector<int> g[NMax];
vector<int> gt[NMax];
vector<bool> viz(NMax, false);
int ord[NMax], nr;
string buffer;
int nrc;

void citire();
void dfs(int);
void dfst(int);
string to_string(int);

int main(){
	int i;
	citire();
	
	for(i = 1; i <= n; i++)
		if(!viz[i]) dfs(i);
	
	for(i = n; i > 0; i--)
		if(viz[ord[i]]){
			dfst(ord[i]);
			buffer += '\n';
			nrc++;
		}
	fout << nrc << '\n';
	fout << buffer;
}

void dfs(int x){
	viz[x] = true;
	for(int i = 0; i < g[x].size(); i++)
		if(!viz[g[x][i]]) dfs(g[x][i]);
	ord[++nr] = x;
}

void dfst(int x){
	viz[x] = false;
	for(int i = 0; i < gt[x].size(); i++)
		if(viz[gt[x][i]]) dfst(gt[x][i]);
	buffer += to_string(x) + ' ';
}

string to_string(int x){
	string s;
	while(x){
		s += (x % 10) + '0';
		x /= 10;
	}
	reverse(s.begin(), s.end());
	return s;
}

void citire(){
	int i, x, y;
	fin >> n >> m;
	for(i = 0; i < m; i++){
		fin >> x >> y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	buffer.reserve(n * 2 + 20);
}