Cod sursa(job #475600)

Utilizator robigiirimias robert robigi Data 7 august 2010 17:31:58
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
// Componente tare conexe.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("ctc.in", "r");
FILE *g=fopen("ctc.out", "w");

typedef struct nod
{
	int x;
	struct nod *adr;
};

typedef struct dflo
{
	int dfn;
	int low;
};

nod *l[100001];
nod *ll[100001];

int n, m;
dflo v[100001];
int viz[100001];
int nr, nrc;
int st[100001];
int s;


void add(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=l[x];
	l[x]=p;
}

void add2(int x, int y)
{
	nod *p=new nod;
	p->x=y;
	p->adr=ll[x];
	ll[x]=p;
}

void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		int x, y;
		fscanf(f, "%d%d", &x, &y);
		add(x, y);
	}
}


int minim(int x, int y)
{
	if (x<y) return x;
	return y;
}


void afis(int x)
{
	++nrc;
	while(st[s+1]!=x)
	{
		add2(nrc, st[s--]);
	}
}


void dfs(int x)
{
	st[++s]=x;
	v[x].dfn=v[x].low=++nr;
	viz[x]=1;
	nod *p=l[x];
	while (p!=NULL)
	{
		if (!viz[p->x])
		{
			dfs(p->x);
			v[x].low=minim(v[x].low, v[p->x].low);
		}
		else
		{
			v[x].low=minim(v[x].low, v[p->x].dfn);
		}
		p=p->adr;
	}
	if (v[x].low==v[x].dfn)
	{
		afis(x);
	}
}


void program()
{
	for (int j=1; j<=n; ++j)
		if (!viz[j])
		{
			nr=0;
			s=0;
			dfs(j);
		}
}



int main()
{
	read();
	program();

	fprintf(g, "%d\n", nrc);
	for (int i=1; i<=nrc; ++i)
	{
		nod *p=ll[i];
		while (p!=NULL)
		{
			fprintf(g, "%d ", p->x);
			p=p->adr;
		}
		fprintf(g, "\n");
	}


	fclose(f);
	fclose(g);
	return 0;
}