Cod sursa(job #1849211)

Utilizator MAlexandruMatei Alexandru MAlexandru Data 17 ianuarie 2017 10:03:32
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
// Componente tare conexe - alg. Kosaraju-Sharir -. O(n+m)

#include <fstream>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g ("ctc.out");


struct nod
  {
      int inf;
      nod *urm;
  } *l[101], *lt[101];

int n, viz[101], st[101], k;

void adaug (nod *&l, int x)
{   nod *c;
    c=new nod;
    c->inf=x;
    c->urm=l;
    l=c;

}

void DF1(int i)
{
    nod *c;
    viz[i]=1;
    for(c=l[i];c!=NULL;c=c->urm)
      if (!viz[c->inf]) DF1(c->inf);
    st[++k]=i;
}

void DF2(int i)
{
    nod *c;
    viz[i]=1;

    for(c=lt[i];c!=NULL;c=c->urm)
      if (!viz[c->inf]) DF2(c->inf);
}

void DF2afij(int i)
{
    nod *c;
    viz[i]=1; g<<i<<" ";
    for(c=lt[i];c!=NULL;c=c->urm)
      if (!viz[c->inf]) DF2afij(c->inf);
}

int main()
{   int i, x, y, m, nr=0;
    f>>n >> m;
    while (f>>x>>y)
     { adaug(l[x],y);
       adaug(lt[y],x);

     }


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

    memset (viz,0, sizeof(viz));

    for (i=n; i>=1;i--)
          if (!viz[st[i]])
            { nr++,DF2(st[i]);

            }
    g << nr << '\n';
    for(i=1;i<=n;i++)viz[i]=0;

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

    memset (viz,0, sizeof(viz));

    for (i=n; i>=1;i--)
          if (!viz[st[i]])
            { DF2afij(st[i]);
              g<<'\n';
            }
    g.close();
    return 0;
}