Cod sursa(job #584924)

Utilizator stef93Stefan Gilca stef93 Data 27 aprilie 2011 12:08:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

vector <int> g[100003],gt[100003],ts,ctc[100003];
int n,m,nrc;
bool u[100003];

void bf(int);
void bft(int);

int main()
{
    int i,j,x,y;
    ifstream in("ctc.in");
    in>>n>>m;
    for(;m;--m)
    {
               in>>x>>y;
               g[x].push_back(y);
               gt[y].push_back(x);
    }
    in.close();
    for(i=1;i<=n;i++)
    if(!u[i])
    bf(i);
    memset(u,0,sizeof(u));
    for(i=ts.size()-1;i>=0;i--)
    if(!u[ts[i]])
    {
              bft(ts[i]);
              nrc++;
    }
    ofstream out("ctc.out");
    out<<nrc<<'\n';
    for(i=0;i<nrc;i++){
    for(j=0;j<ctc[i].size();j++)
    out<<ctc[i][j]<<' ';out<<'\n';}
    out.close();
    return 0;
}

void bf(int k)
{
     int i;
     u[k]=1;
     for(i=0;i<g[k].size();i++)
     if(!u[g[k][i]])
                    bf(g[k][i]);
     ts.push_back(k);
}

void bft(int k)
{
     int i;
     u[k]=1;
     for(i=0;i<gt[k].size();i++)
     if(!u[gt[k][i]])
                    bft(gt[k][i]);
                    ctc[nrc].push_back(k);
}