Cod sursa(job #2667839)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 3 noiembrie 2020 22:35:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define in "ctc.in"
#define out "ctc.out"
#define N 100005

vector <bool> d(N+1, 0);
vector <int> LIST[N], LISTT[N], O, C[N];
int n, m, c;

ofstream fout (out);

void DFS (int x)
{
    d[x] = 1;
    for (unsigned i = 0; i < LIST[x].size(); ++i)
        if (!d[LIST[x][i]])
            DFS (LIST[x][i]);
    O.push_back (x);
}

void DFST (int x)
{
    d[x] = 0;
    C[c].push_back (x);
    for (unsigned i = 0; i < LISTT[x].size(); ++i)
        if (d[LISTT[x][i]])
            DFST (LISTT[x][i]);
}

int main ()
{
    ifstream fin (in);
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        LIST[x].push_back (y);
        LISTT[y].push_back (x);
    }
    fin.close();
    for (int i = 1; i <= n; ++i) {
        sort (LIST[i].begin(), LIST[i].end());
        sort (LISTT[i].begin(), LISTT[i].end());
    }
    for (int x = 1; x <= n; ++x)
        if (!d[x])
            DFS (x);
    for (int x = n-1; x >= 0; --x)
        if (d[O[x]]) {
            DFST (O[x]);
            c++;
        }
    ofstream fout (out);
    fout << c << "\n";
    for (int i = 0; i < c; ++i) {
        for (unsigned j = 0; j < C[i].size(); ++j)
            fout << C[i][j] << " ";
        fout << "\n";
    }
    return 0;
}