Cod sursa(job #866419)

Utilizator ioanapopaPopa Ioana ioanapopa Data 28 ianuarie 2013 00:31:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<cstdio>
#define M 100002
#define min(a,b) ((a)>(b)?(b):(a))

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

struct Graf
 {
		int v;
	Graf *urm;
 };

Graf *a[M], *sol[M];
int nr,n,m,viz[M],niv[M],jos[M],st[M], cap,nivel;

inline void insert(int x, int y, Graf *a[])
 {
	  Graf *p;
	  p=new Graf;
	  p->v = y;
	  p->urm = a[x];
	  a[x] = p;
 }
void citire()
 {
	 
	int x,y;
	fscanf(g,"%d%d",&n,&m);
	while(m--)
   {
	  fscanf(g,"%d%d",&x,&y);
	    insert(x,y,a);
   }
 }

void ctc(int nod)
 {
	st[++cap]=nod;
	Graf *q;
	niv[nod] = jos[nod] = ++nivel;
	for(q=a[nod];q;q=q->urm)
   {
		 if(!niv[q->v])
     {
		  ctc(q->v);
		 jos[nod]=min(jos[nod], jos[q->v]);
     }
		 else if(niv[q->v] > 0) jos[nod]=min(jos[nod], niv[q->v]);
   }
	 if(niv[nod] == jos[nod])
   {
		 ++nr;
	 do
		 {
			   insert(nr, st[cap], sol);
			   niv[st[cap]]=-1;
			  cap--;
	     }
    while(st[cap+1]!=nod);
   }
 }
void afisare()
 {
	fprintf(f,"%d\n",nr);
	 int i;
	Graf *q;
	for(i=1;i<=nr;++i)
	{
		 for(q=sol[i];q;q=q->urm)
		 fprintf(f,"%d ",q->v);
		 fprintf(f,"\n");
    }
 }

int main()
 { 
	 int i;
	 citire();
	 for(i=1;i<=n;++i)
		if(!niv[i])
		  ctc(i);
	afisare();
	return 0;
 }