Cod sursa(job #1889188)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 22 februarie 2017 16:57:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <stack>

#define NMax 100005
#define MMax 200005
#define pb push_back

using namespace std;

vector < int > G1[MMax], G2[MMax], rasp, aux;
bitset < NMax > viz;
stack < int > St;
vector <vector<int> > Ans;

int N, M;

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

void Dfs1(int i)
{
    viz[i]=1;

    vector < int >::iterator it;

    for(it=G1[i].begin(); it!=G1[i].end(); ++it)
    {
        if(!viz[*it])
        {
            Dfs1(*it);
        }
    }

    St.push(i);
}

void Dfs2(int i)
{
    viz[i]=1;

    aux.pb(i);

    vector < int >::iterator it;

    for(it=G2[i].begin(); it!=G2[i].end(); ++it)
    {
        if(!viz[*it])
        {
            Dfs2(*it);
        }
    }
}

void Print()
{
    printf("%d\n", Ans.size());

    for(size_t i = 0; i < Ans.size(); ++i)
    {
        for(size_t j = 0; j < Ans[i].size(); ++j)
            printf("%d ", Ans[i][j]);
        printf("\n");
    }
}

int main()
{

freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);

    Read();

    for(int i=1; i<=N;++i)
        if(!viz[i])
            Dfs1(i);

    viz.reset();

    while(!St.empty())
    {
        int x=St.top();
        St.pop();


       if(viz[x])
            continue;

        aux.clear();
        Dfs2(x);
        Ans.pb(aux);
    }

    Print();

    return 0;
}