Cod sursa(job #1490263)

Utilizator Liviu98Dinca Liviu Liviu98 Data 23 septembrie 2015 01:13:41
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
const int NMax=10002;
vector<int> Graf[NMax],GrafTranspus[NMax],Solution[NMax];
int Componente[NMax],N,M,x,y;
bool mark[NMax];
int ComponentaTare_Conexa;
stack<int> Stiva;

void Read()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        GrafTranspus[y].push_back(x);
    }
}

void DFS1(int nod)
{
    mark[nod]=true;
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
        if(mark[*it]==false)
        DFS1(*it);

    Stiva.push(nod);
}

void DFS2(int nod)
{
    Componente[nod]=ComponentaTare_Conexa;
    Solution[ComponentaTare_Conexa].push_back(nod);
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
        if(Componente[*it]==0)
        DFS2(*it);

    Stiva.push(nod);
}

void Kosaraju()
{
    for(int i=1;i<=N;i++)
        DFS1(i);

    while(Stiva.empty()==false)
    {
        if(Componente[Stiva.top()]==0)
        {
            ComponentaTare_Conexa++;
            DFS2(Stiva.top());
        }
        Stiva.pop();
    }
}

void Write()
{
    printf("%d\n",ComponentaTare_Conexa);
    for(int i=1;i<=ComponentaTare_Conexa;i++)
    {
        for(vector<int>::iterator it=Solution[i].begin();it!=Solution[i].end();it++)
        printf("%d ",*it);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    Read();
    Kosaraju();
    Write();
}