Cod sursa(job #1922167)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 10 martie 2017 16:16:06
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

using namespace std;

vector < int > G1[MMax], G2[MMax], 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].push_back(y);
        G2[y].push_back(x);
    }
}

void DFS1(int x)
{
    viz[x]=1;
    vector < int > ::iterator it;

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

    ST.push(x);
}

void DFS2(int x)
{
    viz[x]=1;
    aux.push_back(x);

    vector < int > ::iterator it;

    for(it=G2[x].begin(); it!=G2[x].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.push_back(aux);
    }

    Print();
    return 0;
}