Cod sursa(job #1491062)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 24 septembrie 2015 18:50:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>

#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int Maxn = 100005;

int n, m, nr_el;
vector <int> G1[Maxn], G2[Maxn], G[Maxn], pos, q, u;

void Read();

void DFP(int x);

void DFM( int x, int which);

void Print();


int main(void)
{
    Read();

    u.resize(n);
    u.assign(u.size(), 0);
    for (int i = 0; i < n; ++ i) if (u[i] == false)
        DFP(i);

    pos.resize(n);
    pos.assign(pos.size(), -1);
    while(q.size())
    {
        if (pos[q.back()] == -1)
        {
            DFM(q.back(), nr_el);
            nr_el ++;
        }
        q.pop_back();
    }
    for (int i = 0; i < n; ++ i)
        G[pos[i]].push_back(i);

    Print();

    return 0;
}
void Read()
{
    int  x, y;

    fin >> n;
    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        x --, y --;
        G1[x].push_back(y);
        G2[y].push_back(x);
    }
}
void Print()
{


    fout << nr_el << '\n';
    for (int i = 0; i < nr_el; ++ i)
    {
        for (auto it : G[i])
            fout << it + 1 << " ";
        fout << '\n';
    }
    fout.close();
}
void DFP(int x)
{
    u[x] = true;
    for (auto it : G1[x] )
        if (u[it] == false)
            DFP(it);
    q.push_back(x);
}
void DFM( int x, int which)
{
    pos[x] = which;
    for (auto it : G2[x])
        if (pos[it] == -1)
            DFM(it, which);
}