Cod sursa(job #2676435)

Utilizator gheorghe_cristiGheorghe Florin Cristi gheorghe_cristi Data 24 noiembrie 2020 11:34:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define dim 100005

using namespace std;

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

int n, m, x, y, fr[dim];
vector<int> a[dim];
vector<int> tr[dim];
vector<int> s;
set<int> comp[dim];

int r;

void dfs(int nod) {
    fr[nod] = 1;

    for(int vecin: a[nod])
        if (!fr[vecin])
            dfs(vecin);

    s.push_back(nod);
}

void Tdfs(int nod) {
    fr[nod] = 1;
    comp[r].insert(nod);

    for(int vecin: tr[nod])
        if (!fr[vecin])
            Tdfs(vecin);
}

int main()
{
    fin >> n >> m;

    while (fin >> x >> y) {
        a[x].push_back(y);
        tr[y].push_back(x);
    }

    for (int i=1;i<=n;++i)
        if (!fr[i])
            dfs(i);

    reverse(s.begin(), s.end());

    memset(fr, 0, sizeof(fr));

    for (int nod: s)
        if (!fr[nod]) {
            r++;
            Tdfs(nod);
        }

    fout << r << "\n";

    for (int i=1;i<=r;++i, fout << "\n")
        for (int it: comp[i])
            fout << it << " ";
}