Cod sursa(job #711143)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 11 martie 2012 14:19:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<fstream>
#include<vector>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector <int> v[lung]; 
vector <int> transp[lung];
vector <int> rasp[lung];
int i,a,b,n,m,nr,timp[lung],ordine[lung],trecut[lung];
bool viz1[lung],viz[lung];

inline void df(int x)
{int i,p=transp[x].size(),max1=0,val;
    if (v[x].size() != 0 && transp[x].size() != 0)
	{   for (i=0;i<p;++i)
		    if (!viz1[transp[x][i]])
	          	if (v[transp[x][i]].size() != 0 && transp[transp[x][i]].size() != 0)
				{	viz1[transp[x][i]] = true;
	                rasp[nr].push_back(transp[x][i]);
	                df(transp[x][i]);
	            }
	}
}
inline void final(int x)
{int i,p=v[x].size();
	timp[++a] = x;
    for (i=0;i<p;++i)
	    if (!viz[v[x][i]])
		    {   viz[v[x][i]] = true;
		        final(v[x][i]);
			}

}
int main()
{   fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b;
	    v[a].push_back(b);
		transp[b].push_back(a);
	}
	a = 0;
	for (i=1;i<=n;++i)
		if (!viz[i])
		{	viz[i] = true;
			final(i);
		}
	for (i=1;i<=n;++i)
    {	trecut[timp[i]] = a;
	    --a;
	}
	for (i=1;i<=n;++i)
		ordine[n-trecut[i]+1] = i;
	for (i=1;i<=n;++i)
		if (!viz1[ordine[i]])
		{   int k=ordine[i];
			++nr;
		    viz1[k] = true;
			rasp[nr].push_back(k);
			df(k);
		}
	fout << nr << '\n';
	int j,p;
	for (i=1;i<=nr;++i)
	{	p=rasp[i].size();
		for (j=0;j<p;++j)
			fout << rasp[i][j] << " ";
		fout << '\n';
    }
	return 0;
}