Cod sursa(job #711480)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 12 martie 2012 10:49:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#include<fstream>
#include<vector>
using namespace std;
#define lung 100005
FILE *fin=fopen("ctc.in","r");
ofstream fout("ctc.out");
int n, m;
vector <int> v[lung], vt[lung],sol[lung];
int poz[lung],nr,rasp;
bool viz[lung];
inline void df(int k)
{   vector <int> ::iterator it;
    viz[k] = true;
	for(it=v[k].begin();it!=v[k].end();++it) 
		if (!viz[*it])
			df(*it);
	poz[++nr] = k;
}
void dft(int k)
{	vector <int> ::iterator it;
    viz[k] = false;
	sol[rasp].push_back(k);
	for(it=vt[k].begin();it!=vt[k].end();++it) 
		if (viz[*it])
			dft(*it);
}
int main()
{int a,b,i,j;
	fscanf(fin,"%d %d",&n,&m); 
    for (i=1;i<=m;++i)
	{   fscanf (fin,"%d %d",&a,&b);
		v[a].push_back(b);
		vt[b].push_back(a);
	}
	for (i=1;i<=n;++i)
		if (!viz[i])
			df(i);
	for (i=n;i>=1;--i)
		if (viz[poz[i]])
		{   ++rasp;
			dft(poz[i]);
		}
	fout << rasp << '\n';
	for (i=1;i<=rasp;++i)
	{   for (j=0;j<sol[i].size();++j)
			fout << sol[i][j] << " ";
		fout << '\n';
	}
	return 0;
}