Cod sursa(job #1833891)

Utilizator Garen456Paun Tudor Garen456 Data 23 decembrie 2016 14:27:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <stack>
#include <vector>
const int nmax=100001;
using namespace std;
FILE *f,*g;
int ct,n,m;
vector <int> G[nmax],Gt[nmax];
vector <int> Ctc[nmax];
stack <int> S;
bool viz[nmax];
void Citire()
{  int i,x,y;
    fscanf(f,"%d%d",&n,&m);
   for(i=1;i<=m;i++)
   { fscanf(f,"%d%d",&x,&y);
       G[x].push_back(y);
       Gt[y].push_back(x);
   }
   fclose(f);
}
void DFSG(int x)
{
    vector <int>::iterator it;
    viz[x]=1;
    for(it=G[x].begin();it!=G[x].end();++it)
        if(viz[*it]==0) DFSG(*it);
    S.push(x);
}
void DFSGT(int x)
{ int i;
    vector <int>::iterator it;
    viz[x]=1;
    for(it=Gt[x].begin();it!=Gt[x].end();++it)
        if(viz[*it]==0) DFSGT(*it);
    Ctc[ct].push_back(x);

}


int main()
{
    g=fopen("ctc.out","w");
    f=fopen("ctc.in","r");
    Citire();
    int i,x;
    for(i=1;i<=n;i++)
        if(viz[i]==0)
        DFSG(i);
    for(i=1;i<=n;i++)
        viz[i]=0;
    while(!S.empty())
    { x=S.top();
    S.pop();
    if(viz[x]==0)
    { ct++;
        DFSGT(x);
    }

    }
    fprintf(g,"%d\n",ct);
    vector <int>::iterator it;
    for(i=1;i<=ct;i++)
    {for(it=Ctc[i].begin();it!=Ctc[i].end();++it)
          fprintf(g,"%d ",*it);
          fprintf(g,"\n");
    }
    return 0;
}