Cod sursa(job #880887)

Utilizator raulstoinStoin Raul raulstoin Data 17 februarie 2013 14:42:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
#include<stack>
#define vec G[nod][i]
#define vec_GT GT[nod][i]
#define NMAX 100005
using namespace std;
int n,m,c;
vector<int> G[NMAX],GT[NMAX],sol[NMAX];
stack<int> S;
bool use[NMAX],use_GT[NMAX];
void read()
{
	ifstream fin("ctc.in");
	fin>>n>>m;
	int x,y;
	for(int i=0;i<m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
	fin.close();
}
void DFS_stack(int nod)
{
	use[nod]=1;
	for(size_t i=0;i<G[nod].size();i++)
		if(!use[vec])
			DFS_stack(vec);
	S.push(nod);
}
void DFS_ctc(int nod)
{
	use_GT[nod]=1;
	for(size_t i=0;i<GT[nod].size();i++)
		if(!use_GT[vec_GT])
			DFS_ctc(vec_GT);
	sol[c].push_back(nod);
}
void print()
{
	ofstream fout("ctc.out");
	fout<<c<<'\n';
	for(int nod=0;nod<c;nod++,fout<<'\n')
		for(size_t i=0;i<sol[nod].size();i++)
			fout<<sol[nod][i]<<' ';
	fout.close();
}
int main()
{
	read();
	for(int i=1;i<=n;i++)
		if(!use[i])
			DFS_stack(i);
	for(;!S.empty();S.pop())
		if(!use_GT[S.top()])
		{
			DFS_ctc(S.top());
			c++;
		}
	print();
	return 0;
}