Cod sursa(job #251866)

Utilizator FlorianFlorian Marcu Florian Data 3 februarie 2009 15:24:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#define M 100002
#define min(a,b) ((a)>(b)?(b):(a))
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
struct Graf
 {
 int v;
 Graf *urm;
 };
Graf *G[M];
Graf *sol[M];
int nr;
int n,m;
int viz[M];
int niv[M];
int low[M];
int st[M], vf;
int nivel;
inline void insert(int x, int y, Graf *G[])
 {
  Graf *p;
  p=new Graf;
  p->v = y;
  p->urm = G[x];
  G[x] = p;
 }
void read()
 {
 int x,y;
  fscanf(f,"%d%d",&n,&m);
  while(m--)
   {
    fscanf(f,"%d%d",&x,&y);
    insert(x,y, G);
   }
 }
void tare_conexe(int nod)
 {
  st[++vf]=nod;
  Graf *q;
  niv[nod] = low[nod] = ++nivel;
  for(q=G[nod];q;q=q->urm)
   {
    if(!niv[q->v])
     {
      tare_conexe(q->v);
      low[nod]=min(low[nod], low[q->v]);
     }
    else if(niv[q->v] > 0) low[nod]=min(low[nod], niv[q->v]);
   }
  if(niv[nod] == low[nod])
   {
    // elimin din stiva pana cand st[vf] != nod
    ++nr;
    do
     {
      insert(nr, st[vf], sol);
      niv[st[vf]]=-1;
      vf--;
     }
    while(st[vf+1]!=nod);
   }
 }
void print()
 {
 fprintf(g,"%d\n",nr);
 int i;
 Graf *q;
 for(i=1;i<=nr;++i)
  {
  for(q=sol[i];q;q=q->urm)
   fprintf(g,"%d ",q->v);
  fprintf(g,"\n");
  }
 }
int main()
 {
 int i;
 read();
 for(i=1;i<=n;++i)
  if(!niv[i]) tare_conexe(i);
 print();
 return 0;
 }