Cod sursa(job #1424523)

Utilizator EpictetStamatin Cristian Epictet Data 24 aprilie 2015 19:01:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#define Max_N 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int N, M, POST_OR[Max_N];
vector < int > VU[Max_N], VD[Max_N];
vector < vector < int > > Sol;
bool viz[Max_N];

void Read_Data();
void DFS_1(int );
void DFS_2(int );
void Solve();
void Write_Data();

int main()
{
    Read_Data();
    Solve();
    Write_Data();
    return 0;
}

void Read_Data()
{
    fin >> N >> M;
    for (int i = 1, x, y; i <= M; i++)
    {
        fin >> x >> y;
        VU[x].push_back(y);
        VD[y].push_back(x);
    }
}

void DFS_1(int nod)
{
    viz[nod] = 1;
    for (vector < int > :: iterator it = VU[nod].begin(); it != VU[nod].end(); it++) {
        if (!viz[*it]) {
            DFS_1(*it);
        }
    }

    POST_OR[++POST_OR[0]] = nod;
}

void DFS_2(int nod)
{
    viz[nod] = 0;
    Sol[Sol.size() - 1].push_back(nod);
    for (vector < int > :: iterator it = VD[nod].begin(); it != VD[nod].end(); it++) {
        if (viz[*it]) {
            DFS_2(*it);
        }
    }
}

void Solve()
{
    for (int i = 1; i <= N; i++) {
        if (!viz[i]) {
            DFS_1(i);
        }
    }

    for (int i = N; i >= 1; i--) {
        if (viz[POST_OR[i]]) {
            Sol.push_back(vector < int > (0));
            DFS_2(POST_OR[i]);
        }
    }
}

void Write_Data()
{
    fout << Sol.size() << '\n';
    for (int i = 0; i < Sol.size(); i++) {
        for (int j = 0; j < Sol[i].size(); j++) {
            fout << Sol[i][j] << ' ';
        }
        fout << '\n';
    }
    fout.close();
}