Cod sursa(job #3262266)

Utilizator solicasolica solica solica Data 9 decembrie 2024 16:58:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e5+9;

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

int n,i,j,m,ctc;

vector<int>g[NMAX],gt[NMAX],comp[NMAX],s;

bool viz[NMAX];

void input ();

void dfs1(int node);

void dfs2(int node);

int main()
{
    input();
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
        {
            dfs1 (i);
        }
    }
    for (i=1; i<=n; i++)
    {
        viz[i]=0;
    }
    while (!s.empty())
    {
        int node=s.back();
        s.pop_back ();
        if (!viz[node])
        {
            ctc++;
            dfs2(node);
        }
    }
    fout<<ctc<<'\n';
    for (i=1; i<=ctc; i++)
    {
        for (auto it : comp[i])
        {
            fout<<it<<' ';
        }
        fout<<'\n';
    }
    return 0;
}

void dfs2(int node)
{
    comp[ctc].push_back (node);
    viz[node]=1;
    for (auto it : gt[node])
    {
        if (!viz[it])
        {
            dfs2(it);
        }
    }
}

void dfs1 (int node)
{
    viz[node]=1;
    for (auto it : g[node])
    {
        if (!viz[it])
        {
            dfs1(it);
        }
    }
    s.push_back (node);
}

void input ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b;
        fin>>a>>b;
        g[a].push_back (b);
        gt[b].push_back (a);
    }
}