Cod sursa(job #499117)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 8 noiembrie 2010 19:53:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 100010

vector <int> g[nmax], gt[nmax], sol[nmax];
int n, m, l, s[nmax], u[nmax], ct;

void dfs(int nod)
{
	u[nod]=1;
	int i;
	for (i=0; i<g[nod].size(); i++) 
		if (!u[g[nod][i]]) dfs(g[nod][i]);
	s[++l]=nod;
}

void dfs2(int nod)
{
	u[nod]=2;
	sol[ct].push_back(nod);
	int i;
	for (i=0; i<gt[nod].size(); i++)
		if (u[gt[nod][i]]!=2) dfs2(gt[nod][i]);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, j, x, y;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	for (i=1; i<=n; i++)
		if (!u[i]) dfs(i);
	for (i=n; i>0; i--)
		if (u[s[i]]!=2)
		{
			ct++;
			dfs2(s[i]);
		}
	printf("%d\n",ct);
	for (i=1; i<=ct; i++)
	{
		for (j=0; j<sol[i].size(); j++) printf("%d ",sol[i][j]);
		printf("\n");
	}
}