Cod sursa(job #928280)

Utilizator Marius96Marius Gavrilescu Marius96 Data 26 martie 2013 13:13:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#include<vector>
using std::vector;

static vector<int> v[100005], rv[100005], ord, ccomp;
static vector<vector<int> > comps;
static bool seen[100005], rseen[100005];

void dfs (int n)
{
	seen[n]=1;
	for(vector<int>::iterator it=v[n].begin();it!=v[n].end();it++)
		if(!seen[*it])
			dfs (*it);
	ord.push_back (n);
}

void rdfs (int n)
{
	ccomp.push_back (n);
	rseen[n]=1;
	for(vector<int>::iterator it=rv[n].begin();it!=rv[n].end();it++)
		if(!rseen[*it])
			rdfs (*it);
}

int main (void)
{
	freopen ("ctc.in","r",stdin);
#ifdef INFOARENA
	freopen ("ctc.out","w",stdout);
#endif

	int n,m;
	scanf ("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf ("%d%d",&x,&y);
		v[x].push_back (y);
		rv[y].push_back (x);
	}

	for(int i=1;i<=n;i++)
		if(!seen[i])
			dfs (i);

	while(!ord.empty()){
		while(!ord.empty() && rseen[ord.back()])
			ord.pop_back();
		if(!ord.empty()){
			ccomp.clear();
			rdfs (ord.back());
			comps.push_back (vector<int>(ccomp));
		}
	}

	printf ("%lu\n",comps.size());
	for(vector<vector<int> >::iterator it=comps.begin();it!=comps.end();it++){
		for(vector<int>::iterator itt=it->begin();itt!=it->end();itt++)
			printf ("%d ",*itt);
		puts ("");
	}
	return 0;
}