Cod sursa(job #1091364)

Utilizator andreea_alexandraAndreea Alexandra andreea_alexandra Data 25 ianuarie 2014 17:14:48
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100001;
fstream fin("grader_test1.in", ios::in);
fstream fout("grader_test1.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;
    int start=*(graphT[x].begin());
    int finish=*(graphT[x].end());
    //for(unsigned int i=0; i<graphT[x].size(); i++)
    for(vector<int>::iterator it=graphT[x].begin(); it!=graphT[x].end(); it++)
    {
        int current=*it;
        if(!vizitat[current])
            dfs1(current);
    }
    stock[0]++;
    stock[stock[0]]=x;
}

void dfs2(int x)
{
    vizitat[x]=true;
    //for(unsigned int i=0; i<graph[x].size(); i++)
    for(vector<int>::iterator it=graph[x].begin(); it!=graph[x].end(); it++)

    {
        if(!vizitat[*it])
            dfs2(*it);
    }
    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(unsigned int j=0; j<comp[i].size(); j++)
        for(vector<int>::iterator it=comp[i].begin(); it!=comp[i].end(); it++)
            fout<<(*it)<<" ";
        fout<<endl;
    }
    return 0;
}