Cod sursa(job #3217888)

Utilizator solicasolica solica solica Data 25 martie 2024 09:13:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define NMAX 100008

int n,i,j,m,nrcomp;

vector<int>s,comp[NMAX];

bool kos=1;

struct graf
{
    bool viz[NMAX];
    vector<int>muchii[NMAX];
    void dfs (int node)
    {
        if (!kos)
        {
            comp[nrcomp].push_back(node);
        }
        viz[node]=1;
        for (auto vec : muchii[node])
        {
            if (!viz[vec])
            {
                dfs(vec);
            }
        }
        if (kos)
        {
            s.push_back(node);
        }
    }
}g,gt;

int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b;
        fin>>a>>b;
        g.muchii[a].push_back(b),gt.muchii[b].push_back(a);
    }
    for (i=1; i<=n; i++)
    {
        if (!g.viz[i])
        {
            g.dfs(i);
        }
    }
    reverse(s.begin(),s.end());
    kos=0;
    for (auto it : s)
    {
        if (!gt.viz[it])
        {
            nrcomp++;
            gt.dfs(it);
        }
    }
    fout<<nrcomp<<'\n';
    for (i=1; i<=nrcomp; i++)
    {
        for (auto it : comp[i])
        {
            fout<<it<<' ';
        }
        fout<<'\n';
    }
    return 0;
}