Cod sursa(job #1228608)

Utilizator danutbodbodnariuc danut danutbod Data 14 septembrie 2014 18:42:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 12.96 kb
#include <fstream>//p O(n+m) (Kosaraju)
#include<vector>
#define Nmax 100001
using namespace std;
ifstream f("ctc.in"); ofstream g("ctc.out");
vector <int> a[Nmax];
vector <int> at[Nmax];vector <int> ctc[Nmax];
int n, m,k,nrc, viz[Nmax],st[Nmax];
void df (int nod)
{
  int i;
  viz[nod] = 1;
  for (i = 0; i < a[nod].size(); i++)
    if (viz[a[nod][i]]==0) df(a[nod][i]);
  st[++k]=nod;
}

void dft (int nod) //df transpus
{
  int i;
  viz[nod] = 1;ctc[nrc].push_back(nod);
  for (i = 0; i < at[nod].size(); i++)
    if (viz[at[nod][i]]==0)
       dft(at[nod][i]);

}

int main() {
  int i, j, x, y;
  f >> n >> m;
  for (i = 1; i <= m; i++)
  {
    f >> x >> y;
    a[x].push_back(y);
    at[y].push_back(x);
  }
//for(i=1;i<=n;i++){
// for (j=0; j<at[i].size();j++)
//   g<<at[i][j]<<" ";
// g<<'\n';
//}
for (i = 1; i <= n; i++)
    if (viz[i]==0)  df(i);
//for(i=1;i<=n;i++)g<<st[i]<<" ";g<<endl;
 for (i = 1; i <= n; i++) viz[i]=0;
 //memprat cu vector si numarat
 nrc=0;
 for (i = n; i >=1; i--)
    if (viz[st[i]]==0)  {
             nrc++;
             dft(st[i]);
            }
g<<nrc<<'\n';
for(i=1;i<=nrc;i++){
 for (j=0; j<ctc[i].size();j++)
   g<<ctc[i][j]<<" ";
 g<<'\n';
}
  return 0;
}


//#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;
//}

//#include <fstream>
//#define Nmax 1025
//using namespace std;
//ifstream f("cmlsc.in");
//ofstream g("cmlsc.out");
//int n,m,b[Nmax],a[Nmax],d[Nmax][Nmax],sol[Nmax],t,i,j;
//
//int main(void)
//{
//    f>>n>>m;
//    for(i=1;i<=n;i++)f>>a[i];
//    for(i=1;i<=m;i++)f>>b[i];
//
//    for(i=1;i<=n;i++)
//       for(j=1;j<=m;j++)
//            if (a[i]==b[j])
//                d[i][j]=1+d[i-1][j-1];
//            else
//                d[i][j] = max(d[i-1][j],d[i][j-1]);
////    for(i=1;i<=n;i++){
////       for(j=1;j<=m;j++) g<<d[i][j]<<" ";
////       g<<'\n';
////    }
//    g<<d[n][m]<<'\n';
//    i=n;j=m;
//    while(i&&j)
//        if (a[i]==b[j])
//            {sol[++t]=a[i];i--;j--;}
//        else if (d[i-1][j]<d[i][j-1])j--;
//             else i--;
//
//   for(i=t;i>=1;i--)
//       g<< sol[i]<<" ";
//
//    return 0;
//}
//


//#include <fstream>
//using namespace std;
//ifstream f("euclid2.in");
//ofstream g("euclid2.out");
//long long x,y,n,i;
//long long cmmdc_scaderi(int a, int b) //80p(timpul)
//{
//    int r;
//    while(a!=b)
//    if(a>b)
//      a=a-b;
//     else
//      b=b-a;
//    return a;
//}
//long long cmmdc(int a, int b) //100p
//{
//    int r;
//    while(b)   {      r=a%b;  a=b;   b=r;   }
//    return a;
//}
//int main(){
// f>>n;
// for(i=1;i<=n;i++){
// f>>x>>y;
// g<<cmmdc(x,y)<<'\n';
// }
//return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream f("euclid3.in");
//ofstream g("euclid3.out");
//int a1,a2,b1,b2;
//int xGood,yGood;
//int cmmdc1(int a,int b)   //cmmdc varianta mea!!!!!
//{
//    while(a)
//    {
//        if(a<b)swap(a,b);
//        a=a%b;
//    }
//    return b;
//}
//int cmmdc2(int a,int b)   //cmmdc varianta mea!!!!!
//{
//    while(b)
//    {
//        if(b<a)swap(a,b);
//        b=b%a;
//    }
//    return a;
//}
//int euclid_extins1(int a ,int b)//cu scaderi repetate  20p(timpul!!!!)
//{
//    a1=1,b1=0,a2=0,b2=1;
//    while (a&&b)
//    {
//        if (a>b)
//        {
//            a-=b;
//            a1-=a2;
//            b1-=b2;
//        }
//        else
//        {
//            b-=a;
//            a2-=a1;
//            b2-=b1;
//        }
//    }
//    if (a) xGood=a1,yGood=b1;
//    else xGood=a2,yGood=b2;
//    if (a) return a;
//    else return b;
//}
//
//
//int euclid_extins2(int a ,int b)//cu impartiri  repetate  100p
//{
//    a1=1,b1=0,a2=0,b2=1;
//    while (a&&b)
//    {
//        if (a>b)
//        {
//            a1-=a2*(a/b);
//            b1-=b2*(a/b);
//            a%=b;
//        }
//        else
//        {
//            a2-=a1*(b/a);
//            b2-=b1*(b/a);
//            b%=a;
//        }
//    }
//    if (a) xGood=a1,yGood=b1;
//    else xGood=a2,yGood=b2;
//    if (a) return a;
//    else return b;
//}
//
//
//
//
//int euclid_extins3(int a ,int b)//cu impartiri repetate 100p
//{
//    int sa1,sb1;  //a(a1,b1)   b(a2,b2)
//    a1=1,b1=0;    //a=1*a+0*b
//    a2=0,b2=1;    //b=0*a+1*b
//    int rest,cat;
//    while (b)
//    {
//        //if(a<b){ swap(a,b); swap(a1,a2); swap(b1,b2); }
//        rest=a%b;
//        cat=a/b;
//        a=b;
//        sa1=a1;
//        sb1=b1;
//        a1=a2;
//        b1=b2;//se salveaza (a1,b1) si a=b
//        b=rest;
//        a2=sa1-=cat*a2;
//        b2=sb1-=cat*b2;//se calculeaza noul b(a2,b2)
//    }                                 //impartire = scaderi repetate de "cat" ori
//    xGood=a1,yGood=b1;
//    return a;
//}
//
//int main()
//{
//    int i,nrt;
//    f>>nrt;
//
//    for(i=1; i<=nrt; i++)
//    {
//        int a,b,c;
//        f>>a>>b>>c;
//        int CMMDC=euclid_extins3(a,b);
//
//        if (c%CMMDC==0)
//        {
//            g<<xGood*(c/CMMDC)<<" "<<yGood*(c/CMMDC)<<'\n';
//        }
//        else
//            g<<0<<" "<<0<<'\n';
//    }
//    return 0;
//}
//#include <iostream> // var Dutu
//#include <fstream>
//using namespace std;
//ifstream f("euclid3.in");
//ofstream g("euclid3.out");
//int a1,a2,b1,b2;
//int xGood,yGood;
//int euclid_extins3(int a ,int b)//cu impartiri  repetate  100p
//{
//    a1=1,b1=0,a2=0,b2=1;
//    while (a&&b)
//    {
//        if (a>b)
//        {
//            a1-=a2*(a/b);
//            b1-=b2*(a/b);
//            a%=b;
//        }
//        else
//        {
//            a2-=a1*(b/a);
//            b2-=b1*(b/a);
//            b%=a;
//        }
//    }
//    if (a) xGood=a1,yGood=b1;
//    else xGood=a2,yGood=b2;
//    if (a) return a;
//    else return b;
//}
//
//
//int main()
//{
//    int i,nrt;
//    f>>nrt;
//    for(i=1; i<=nrt; i++)
//    {
//        int a,b,c;
//        f>>a>>b>>c;
//        if (c<0) a=-a,b=-b,c=-c;
//
//
//        int CMMDC=euclid_extins3(a>0?a:-a,b>0?b:-b);
//
//        if (a<0) xGood=-xGood;
//        if (b<0) yGood=-yGood;
//
//        if (c%CMMDC==0)
//        {
//            g<<xGood*(c/CMMDC)<<" "<<yGood*(c/CMMDC)<<'\n';
//        }
//        else
//            g<<0<<" "<<0<<'\n';
//    }
//    return 0;
//}


//#include <stdio.h>
//int a[100],x[100],n,i,k;
// int main(void){
//
// printf("n=");scanf("%d",&n);
// printf("Radacinile:\n");
// for(i=1;i<=n;i++){
//  printf("x[%d]=",i);scanf("%d",&x[i]);a[i]=0;
// }
// a[0]=1;a[n]=0;
// for(k=1;k<=n;k++){
//  for(i=k;i>=1;i--)
//	a[i]=a[i-1]-a[i]*x[k];
//  a[0]*=-x[k];
// }
// for(i=n;i>=0;i--) printf("a[%d]=%d ",i,a[i]);
// return 0;
//}