Cod sursa(job #1889843)

Utilizator calin1Serban Calin calin1 Data 22 februarie 2017 21:48:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#define N 100005

using namespace std;

int n, m, nr;

vector <int> G[N];
vector <int> inversa[N];

vector <int> de_afisat[N];

bitset <N> viz;

stack <int> S;

void recursiva(int k, vector <int> G[] , int p)
{
    viz[k] = true;

    if(!p)
    {
        de_afisat[nr].push_back(k);
    }

    vector <int> ::iterator it;

    for(it = G[k].begin() ; it != G[k].end(); ++it)
    {
        if(!viz[*it])
        {
            recursiva(*it, G, p);
        }
    }
    if(p)
    {
        S.push(k);
    }
}

void afisare()
{
    printf("%d\n",nr);

    int l;

    for(int i = 0 ; i < nr ; ++i)
    {
        l = de_afisat[i].size();

        for(int j = 0 ; j < l ; ++j)
        {
            printf("%d ",de_afisat[i][j]);
        }
        printf("\n");
    }
}

int prelucrare()
{

    for(int i = 1 ; i <= n ; ++i)
    {
        if(!viz[i])
        {
            recursiva(i,G,1);
        }
    }

    viz.reset();

    int tmp;

    while(!S.empty())
    {
        tmp = S.top();

        S.pop();

        if(!viz[tmp])
        {
            recursiva(tmp,inversa,0);

            nr++;
        }
    }

    afisare();
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    int a, b;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d\n",&a,&b);

        G[a].push_back(b);
        inversa[b].push_back(a);
    }

    prelucrare();

}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();

    return 0;
}