Cod sursa(job #3209125)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 1 martie 2024 22:48:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int n,m,i,x,y,conex,viz[100002];
vector <int> L[100002],LT[100002],sort_top,SOL[100002];
void dfs(int nod)
{
    viz[nod]=1;
    for(auto j:L[nod])
        if(!viz[j])
            dfs(j);
    sort_top.push_back(nod);
}
void dfst(int nod)
{
    viz[nod]=1;
    SOL[conex].push_back(nod);
    for(auto j:LT[nod])
        if(!viz[j])
            dfst(j);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
        LT[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    for(i=1;i<=n;i++)
        viz[i]=0;
    for(i=n-1;i>=0;i--)
        if(!viz[sort_top[i]])
        {
            conex++;
            dfst(sort_top[i]);
        }
    fout<<conex<<"\n";
    for(i=1;i<=conex;i++)
    {
        sort(SOL[i].begin(),SOL[i].end());
        for(auto j:SOL[i])
            fout<<j<<" ";
        fout<<"\n";
    }
    return 0;
}