Cod sursa(job #3251740)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 26 octombrie 2024 18:46:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include<bits/stdc++.h>

using namespace std;

const int dim = 1e5 + 55;

int n, m, x, y, comp;

vector<int>noduri[dim], conex[dim], invnod[dim];

bitset<dim>viz;
stack<int>stiva;

void dfs(int nod)
{
    viz[nod] = 1;
    for(auto it: noduri[nod])
        if(!viz[it])
            dfs(it);

    stiva.push(nod);
}
void dfsdoi(int nod)
{
    viz[nod] = 1;

    conex[comp].push_back(nod);

    for(auto it: invnod[nod])
        if(!viz[it])
            dfsdoi(it);
}

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

int32_t main(int argc, char * argv[])
{
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        noduri[x].push_back(y);
        invnod[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);

    viz.reset();

    while(!stiva.empty())
    {
        int i = stiva.top();
        stiva.pop();
        if(!viz[i])
        {
            comp++;
            dfsdoi(i);
            sort(conex[comp].begin(), conex[comp].end());
        }
    }

    fout << comp << '\n';

    for(int i = 1; i <= comp; ++i, fout << '\n')
        for(int j = 0; j < conex[i].size(); ++j)
            fout << conex[i][j] << " ";
    return 0;

}