Cod sursa(job #1040573)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 24 noiembrie 2013 17:39:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=100005;
int n,m,no;
vector<int> g[MAXN],t[MAXN],sol[MAXN];
stack<int> s;
bool uz[MAXN];
void read()
{
	ifstream fin("ctc.in");
	fin>>n>>m;
	int i,x,y;
	for (i=1; i<=m; ++i)
	{
		fin>>x>>y;
		g[x].push_back(y);
		t[y].push_back(x);
	}
	fin.close();
}
void dfsg(int u)
{
	s.push(u);
	uz[u]=true;
	for (vector<int>::iterator v=g[u].begin(); v!=g[u].end(); ++v)
	{
		if (!uz[*v])
			dfsg(*v);
	}
}
void dfst(int u)
{
	uz[u]=true;
	sol[no].push_back(u);
	for (vector<int>::iterator v=t[u].begin(); v!=t[u].end(); ++v)
	{
		if (!uz[*v])
		{
			dfst(*v);
		}
	}
}
void solve()
{
	int i;
	for (i=1; i<=n && s.size()!=n; ++i)
	{
		if (!uz[i])
			dfsg(i);
	}
	for (i=1; i<=n; uz[i]=0, ++i);
	while (!s.empty())
	{
		if (!uz[s.top()])
		{
			++no;
			dfst(s.top());
		}
		s.pop();
	}
}
void write()
{
	ofstream fout("ctc.out");
	fout<<no<<'\n';
	for (int i=1; i<=no; ++i)
	{
		for (vector<int>::iterator j=sol[i].begin(); j!=sol[i].end(); ++j)
		{
			fout<<*j<<' ';
		}
		fout<<'\n';
	}
	fout.close();
}
int main()
{
	read();
	solve();
	write();
	return 0;
}