Cod sursa(job #873192)

Utilizator danutbodbodnariuc danut danutbod Data 6 februarie 2013 22:27:15
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.12 kb
#include<fstream>////var IV 100p Tarjan O(n+m)
#define M 100003
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct Nod
 {   int v; Nod *urm; };
Nod *a[M], *sol[M];
int nr,n,m,viz[M],index[M],lowlink[M],stiva[M],cap,nivel;

 void insert(int x, int y, Nod *a[])
 {
      Nod *p;
      p=new Nod;
      p->v = y;
      p->urm = a[x];
      a[x] = p;
 }
void citire()
 {

    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;  insert(x,y,a);
    }
 }
void afisare()
 {
    int i;
    Nod *q;
    g<<nr<<'\n';
    for(i=1;i<=nr;++i)
      {
         for(q=sol[i];q;q=q->urm)
         g<<q->v<<" ";
         g<<'\n';
      }
 }
void Tarjan(int nod)
 {
    Nod *p;
    stiva[++cap]=nod;
    index[nod] = lowlink[nod] = ++nivel;
    for(p=a[nod];p;p=p->urm)
    {
         if(index[p->v]==0)
            {
             Tarjan(p->v);
             lowlink[nod]=min(lowlink[nod],lowlink[p->v]);
            }
         else
           // if(index[p->v] > 0)
            lowlink[nod]=min(lowlink[nod],index[p->v]);
    }
     if(index[nod] == lowlink[nod])
       {
         ++nr;
         do
           {
               insert(nr, stiva[cap], sol);
               //index[stiva[cap]]=-1;
               cap--;
           }
         while(stiva[cap+1]!=nod);
       }
 }

int main()
 {
     int i;
     citire();
     for(i=1;i<=n;++i)
        if(index[i]==0)  Tarjan(i);
    afisare();
    return 0;
 }
//#include <fstream>//var III 60p O(n^2)  cu liste de adiacenta (timp depasit)
//#define Nmax 100003
//using namespace std;
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//struct Nod { int v; Nod*urm;};
//Nod* L[Nmax], *LT[Nmax], *comp[Nmax];
//int post[Nmax],n,m,nrc,x,y;
//int viz[Nmax];
//
//void dfp(int nod)//df plus
//{
//     Nod *p;
//     viz[nod] = 1;//se bifeaza cu 1 nodurile cu +
//     p=L[nod];
//     while(p)
//      {
//         if (viz[p->v]==0) dfp(p->v);
//         p=p->urm;
//      }
//}
//
//void dfm(int nod)//df minus
//{
//     Nod *p;
//     viz[nod] = 2;//se bifeaza cu 2 nodurile cu -
//     Nod *q = new Nod;      //se pune componenta tare conexa
//     q->v = nod;q->urm=0;
//     q->urm = comp[nrc];
//     comp[nrc] = q;
//     p=LT[nod];
//     while(p)
//     {
//        if (viz[p->v]==1) dfm(p->v);
//        p=p->urm;
//     }
//}
//
//int main()
//{
//    Nod * q,*p; int i,j;
//   f>>n>>m;
//   for (int i=1;i<=m;i++)
//    {
//        f>>x>>y;
//        q = new Nod;       //construire liste de adiacenta
//        q->v=y;q->urm=0;   //pentru graful normal
//        q->urm=L[x];       //L  lista
//        L[x]=q;
//
//        q = new Nod;       //construire liste de adiacenta
//        q->v=x;q->urm=0;   //pentru graful transpus
//        q->urm=LT[y];      //LT lista transpusa
//        LT[y]=q;
//    }
//  for (i = 1; i <= n; i++)
//    if (viz[i]==0)
//    {
//      nrc++;
//      dfp(i);   //se bifeaza nodurile vecine cu i ci +
//      dfm(i);   //se bifeaza nodurile vecine pe graful transpus
//               vecine cu i cu -(astea sunt deja componenete)
//          for (j = 1; j <= n; j++)
//                if(viz[j]==1) viz[j]=0; //se pun pe 0 viz. nodurilor nefolosite
//    }
//
//  g<<nrc<<endl;
//  for (int i=1;i<=nrc;i++)//afisare componente
//    {
//        p=comp[i];
//        while(p){g<<p->v<<' ';p=p->urm;}
//        g<<endl;
//    }
//
//    return 0;
//}
//#include <fstream>//var II  60p (timp depasit)??
//#define Nmax 100003
//using namespace std;
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//struct Nod { int v; Nod*urm;};
//Nod* l[Nmax], *l2[Nmax], *comp[Nmax];
//int post[Nmax],n,m,cnt,x,y;
//int viz[Nmax];
//
//void df(int nod)
//{
//     Nod *p;
//     viz[nod] = 1;
//     p=l[nod];
//     while(p)
//      {
//         if (viz[p->v]==0) df(p->v);
//         p=p->urm;
//      }
//    post[++post[0]] = nod;
//}
//
//void df2(int nod)
//{
//     Nod *p;
//     viz[nod] = 0;
//     Nod *q = new Nod;
//     q->v = nod;q->urm=0;
//     q->urm = comp[cnt];
//     comp[cnt] = q;
//     p=l2[nod];
//     while(p)
//     {
//        if (viz[p->v]==1) df2(p->v);
//        p=p->urm;
//     }
//}
//
//int main()
//{
//    Nod * q,*p;
//    f>>n>>m;
//    for (int i=1;i<=m;++i)
//    {
//        f>>x>>y;
//        q = new Nod;
//        q->v=y;q->urm=0;
//        q->urm=l[x];
//        l[x]=q;
//
//        q = new Nod;
//        q->v=x;q->urm=0;
//        q->urm=l2[y];
//        l2[y]=q;
//    }
//
//    for (int i=1;i<=n;++i)
//       if (viz[i] == 0) df(i);
////for (int i = 1; i <= n; i++) g<<viz[i]<<' ';g<<endl;
////for (int i = 1; i <= n; i++) g<<post[i]<<' ';g<<endl;
//    for (int i=n;i>0;--i)
//    if (viz[post[i]] == 1) { ++cnt; df2(post[i]); }
//    g<<cnt<<endl;
//
//    for (int i=1;i<=cnt;i++)
//    {
//        p=comp[i];
//        while(p){g<<p->v<<' ';p=p->urm;}
//        g<<endl;
//    }
//
//    return 0;
//}
//#include <fstream>//30p O(n^3) ( probleme-timp si memorie)
//using namespace std;
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//int n, m, nrc, a[4000][4000], suc[4000], pred[4000];
//void df (int nod, int nrc)
//{
//  int i;
//  suc[nod] = nrc;
//  for (i = 1; i <= n; i++)
//    if (a[nod][i] == 1 and suc[i] == 0) df(i,nrc);
//}
//
//void dft (int nod,int nrc) //df transpus
//{
//  int i;
//  pred[nod]=nrc;
//  for (i = 1; i <= n; i++)
//    if (a[i][nod] == 1 and pred[i] == 0) dft(i,nrc);
//}
//
//int main() {
//  int c,i, j, x, y;
//  f >> n >> m;
//  for (i = 1; i <= m; i++)
//  {
//    f >> x >> y;
//    a[x][y] = 1;
//  }
//
//for (i = 1; i <= n; i++)
//    if (suc[i]==0)
//    {
//      nrc++;
//      df(i,nrc);
//      dft(i,nrc);
//      for (j = 1; j <= n; j++)
//        if (suc[j]!=pred[j]) suc[j]=pred[j]=0;
//    }
//  g << nrc << endl;
//
//for (c = 1; c <= nrc; c++)
//  {
//    for (i = 1; i <= n; i++)
//      if(suc[i]==c) g << i << ' ';
//    g << endl;
//  }
////   for (i = 1; i <= n; i++) g<<suc[i]<<' ';g<<endl;
////  for (i = 1; i <= n; i++) g<<pred[i]<<' ';g<<endl;
//  return 0;
//}