Cod sursa(job #2868439)

Utilizator marcpopPop Marc Alexandru marcpop Data 10 martie 2022 22:21:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>

#define pb push_back

using namespace std;

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

int n, m, a, b, nr;

vector<vector<int> > v;
vector<vector<int> > vt;
vector<int> s;
vector<int> e[100000];

vector<bool> viz;

void dfs1(int start) {

    viz[start] = 1;

    for (int i=0; i<v[start].size(); i++) {

        if (!viz[v[start][i]]) {
            dfs1(v[start][i]);
        }

    }

    s.pb(start);

}

void dfs2(int start, int nr) {

    viz[start] = 1;
    e[nr].pb(start);

    for (int i=0; i<vt[start].size(); i++) {

        if (!viz[vt[start][i]]) {
            dfs2(vt[start][i], nr);
        }

    }

}

int main()
{

    fin>>n>>m;

    v = vector<vector<int> >(n+1);
    vt = vector<vector<int> >(n+1);

    for (int i=1; i<=m; i++) {

        fin>>a>>b;

        v[a].pb(b);
        vt[b].pb(a);
    }

    viz = vector<bool>(n+1, 0);

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

    viz = vector<bool>(n+1, 0);


    for (int i=s.size()-1; i>=0; i--) {

        if(!viz[s[i]]) {
            nr++;
            dfs2(s[i], nr);
        }

    }

    fout<<nr<<"\n";

    for (int i=1; i<=nr; i++) {
        for (int j=0; j<e[i].size(); j++) {
            fout<<e[i][j]<<" ";
        }
        fout<<"\n";
    }

    return 0;
}