Cod sursa(job #1607209)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 20 februarie 2016 21:48:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
# include <fstream>
# include <vector>
# include <bitset>

# define MAXN 100010
# define pb   push_back

using namespace std;

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

vector<int> nl, l[MAXN], lt[MAXN], ctc[MAXN];
bitset<MAXN> viz;
int sol;
int n, m, x, y;

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

    nl.pb(nod);
}

void dfs2(int nod) {
    ctc[sol].pb(nod);
    viz[nod] = 0;
    for (vector<int>::iterator it = lt[nod].begin(); it!=lt[nod].end(); ++it)
        if (viz[*it])
            dfs2(*it);
}

int main() {
    fin >> n >> m;
    for (int i=1; i<=m; ++i) {
        fin >> x >> y;
        l[x].pb(y); // gr normal
        lt[y].pb(x); // gr traspuns
    }

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

    for (vector<int>::iterator it = nl.end(); it!=nl.begin(); --it)
        if (viz[*it]) {
            ++sol;
            dfs2(*it);
        }

    fout << sol << "\n";
    for (int i=1; i<=sol; ++i) {
        for (vector<int>::iterator it = ctc[i].begin(); it!=ctc[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }

    return 0;
}