Cod sursa(job #1833598)

Utilizator passwordCiaciru Ana Maria password Data 22 decembrie 2016 18:55:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <stack>
#include <vector>
#define mmax 200001
const int nmax=1000000;
using namespace std;
FILE *f, *g;

int n,m;
bool viz[nmax];
bool viz1[nmax];
vector <int> V[mmax];
vector <int> V1[mmax];
vector <int> Vt[mmax];
stack <int> S;

void read()
{ int i,x,y;
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;++i)
    { fscanf(f,"%d%d",&x,&y);
      /* fprintf(g,"%d ",x);
       fprintf(g,"%d",y);
       fprintf(g,"\n"); */
      V[x].push_back(y);
      Vt[y].push_back(x);
    }
 fclose(f);
}

void dfs(int x)
{ int i;
  vector <int>::iterator it;
  viz[x]=1;
  for(it=V[x].begin();it!=V[x].end();++it)
     if(!viz[*it]) dfs(*it);
  S.push(x);
}

void dfs2(int x, int nr)
{ int i;
  vector <int>::iterator it;
  viz1[x]=1;
  for(it=Vt[x].begin();it!=Vt[x].end();++it)
     if(!viz1[*it]) dfs2(*it,nr);
  V1[nr].push_back(x);
}


int main()
{
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    read();

    for(int i=1;i<=n;i++)
        if(!viz[i]) dfs(i);

    int x,nr=0;
    while(!S.empty())
    { x=S.top();
      S.pop();
      if(!viz1[x]){nr++;
                  dfs2(x,nr);}
    }
    fprintf(g,"%d",nr);
    fprintf(g,"\n");
   vector <int>::iterator it;
   for(int i=1;i<=n;i++)
      {for(it=V1[i].begin();it!=V1[i].end();++it)
              fprintf(g,"%d ",*it);
        fprintf(g,"\n");
      }
    return 0;
}