Cod sursa(job #645014)

Utilizator valentina506Moraru Valentina valentina506 Data 7 decembrie 2011 23:32:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<vector>
#define pb push_back
using namespace std;
int n,m,i,j,uz[100001],x,y,b[100001],n1,nr;
vector<int> a[100001];
vector<int> at[100001];
vector<int> sol[100001];

void df(int x)
{
	int i;
	uz[x]=1;
	for(i=0;i<a[x].size();++i)
		if(!uz[a[x][i]])
			df(a[x][i]);
		b[++n1]=x;
}

void dft(int x)
{
	int i;
	uz[x]=0;
	sol[nr].pb(x);
	for(i=0;i<at[x].size();++i)
		if(uz[at[x][i]])
			dft(at[x][i]);
}

int main()
{
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		a[x].pb(y);
		at[y].pb(x);
	}
	
	for(i=1;i<=n;++i)
		if(!uz[i])
			df(i);
		for(i=n;i>0;--i)
			if(uz[b[i]])
			{
				++nr;
				dft(b[i]);
			}
			
			g<<nr<<"\n";
			for(i=1;i<=nr;++i)
			{
				for(j=0;j<sol[i].size();++j)
					g<<sol[i][j]<<" ";
				g<<"\n";
			}
			return 0;
}