Cod sursa(job #1734932)

Utilizator stefanchistefan chiper stefanchi Data 28 iulie 2016 15:47:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bitset>
#include <vector>
#include <stack>
#include <stdio.h>
#define N 100010
using namespace std;
vector <int> graf[N];
vector <int> inv_graf[N];
vector <int> solutie[N];
stack <int> coada;
bitset <N> v;
int n , m ;

void read()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= m ; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        graf[a].push_back(b);
        inv_graf[b].push_back(a);
    }
}

void parcurg(int x)
{
   vector <int> :: iterator it;
    v[x] = true;
    for(it = graf[x].begin(); it != graf[x].end(); ++it)
    {
        if(!v[*it])
            parcurg(*it);
    }
    coada.push(x);
}

void parcurg_inv(int x , int contor)
{
    solutie[contor].push_back(x);
    vector <int> :: iterator it;
    v[x] = true;
    for(it = inv_graf[x].begin(); it != inv_graf[x].end(); ++it)
    {
        if(!v[*it])
            parcurg_inv(*it, contor);
    }
}

void afisam(int lim)
{
    for(int i = 0 ; i < lim ; i++)
    {
        for(vector <int> :: iterator it = solutie[i].begin() ; it != solutie[i].end() ; ++it)
            printf("%d ",*it);
        printf("\n");
    }
}

void rezolvare()
{
    int numar = 0;
    for(int i = 1; i <= n ; i++)
    {
      if(!v[i])
            parcurg(i);
    }
    v = false;
    while(!coada.empty())
    {
        int x = coada.top();
        coada.pop();
        if(!v[x])
        {
            parcurg_inv(x,numar);
            numar++;
        }
    }
    printf("%d\n",numar);
    afisam(numar);
}

int main()
{
    read();
    rezolvare();
    return 0;
}