Cod sursa(job #342064)

Utilizator bog29Antohi Bogdan bog29 Data 20 august 2009 14:53:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<vector>
#define dmax 100003
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,c[dmax],po[dmax],p,nrc;
bool viz[dmax];
vector<int>g[dmax];
vector<int>gt[dmax];
vector<int>ctc[dmax];
vector<int>::iterator it;

void dfs(int k)
{	vector<int>::iterator z;
	viz[k]=1;
	for(z=g[k].begin();z<g[k].end();z++)
	{	if(viz[*z]==0)
			dfs(*z);
	}
	po[p++]=k;	
}

void dfst(int k)
{	vector<int>::iterator g;
	viz[k]=0;
	ctc[nrc].push_back(k);
	for(g=gt[k].begin();g<gt[k].end();g++)
		if(viz[*g])
			dfst(*g);
}

int main()
{	int i,x,y;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>x>>y;
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	in.close();
	
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			dfs(i);
		
	for(i=n;i>=1;i--)
		if(viz[po[i]]==1)
		{	nrc++;
			dfst(po[i]);
		}
		
	out<<nrc<<'\n';
	for(i=1;i<=nrc;i++)
	{	for(it=ctc[i].begin();it<ctc[i].end();it++)
			out<<*it<<" ";
		out<<'\n';
	}	
	out.close();
	return 0;
}