Cod sursa(job #1091270)

Utilizator andreea_alexandraAndreea Alexandra andreea_alexandra Data 25 ianuarie 2014 15:49:22
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100000;
fstream fin("ctc.in", ios::in);
fstream fout("ctc.out", ios::out);
vector <int> graph[N_MAX], graphT[N_MAX], comp[N_MAX];
int   k=0, stock[N_MAX];
bool vizitat[N_MAX];

int N, M;


void citire()
{
    int x, y;
    fin>>N;
    fin>>M;
    for(int i=0; i<M; i++)
    {
        fin>>x>>y;
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }
}

void dfs1(int x)
{
    vizitat[x]=true;
    for(int i=0; i<graphT[x].size(); i++)
    {
        if(!vizitat[graphT[x][i]])
            dfs1(graphT[x][i]);
    }
    stock[0]++;
    stock[stock[0]]=x;
}

void dfs2(int x)
{
    vizitat[x]=true;
    for(int i=0; i<graph[x].size(); i++)
    {
        if(!vizitat[graph[x][i]])
            dfs2(graph[x][i]);
    }
    comp[k].push_back(x);
}

void SortareTop()
{
    for(int i=1; i<=N; i++)
        if(!vizitat[i])
            dfs1(i);
}

int main()
{
    citire();
    SortareTop();
    memset(vizitat, false, sizeof(vizitat));
    for(int i=N; i>0; i--)
    {
        if(!vizitat[stock[i]])
        {
            k++;
            dfs2(stock[i]);
        }
    }
    fout<<k<<endl;
    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<comp[i].size(); j++)
            fout<<comp[i][j]<<" ";
        fout<<endl;
    }
    return 0;
}