Cod sursa(job #2939503)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 13 noiembrie 2022 19:54:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#include <algorithm>

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

void dfs_org(int);
void dfs_trn(int);

vector <int> v[100005], t[100005], dv, ctr[100005];
int ct[100005], f[100005];
int dfss, ctc, n, m;

int main()
{
    int i, a, b;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        t[b].push_back(a);
    }
    for(i=1; i<=n; i++)
    {
        if(ct[i]==0) 
        {
            if(dv.size()) 
            {
                dv.clear();
            }
            dfss++;
            dfs_org(i);
            for(int j=int(dv.size())-1; j>=0; j--) //merg invers in vectorul format in dfs_org
            {
                if(f[dv[j]]==dfss && ct[dv[j]]==0) //daca nu are comp. tare con. , ii gasesc
                {
                    //fout << '\n';
                    ctc++;
                    dfs_trn(dv[j]);
                }
            }
        }
    }
    fout<<ctc<<'\n';
    for(i=1; i<=ctc; i++)
    {
        sort(ctr[i].begin(), ctr[i].end());
        for(auto j:ctr[i]) fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}

//ma duc in toate nodurile posibile si le marchez ca vizitate
void dfs_org(int nod)
{
    //fout<<nod<<' ';
    f[nod]=dfss;
    for(auto i:v[nod]) 
    {
        if(f[i]==0 && ct[i]==0)
        {
            dfs_org(i);
        }
    }
    dv.push_back(nod);
}

//ma duc prin toate nodurile posibile din graful transpus si daca sunt vizitate in ambele parcurgeri, atunci sunt comp tare conexa comuna
void dfs_trn(int nod)
{
    //fout<<nod<<' ';
    ct[nod]=ctc;
    ctr[ctc].push_back(nod);
    for(auto i:t[nod]) 
    {
        if(f[i]==dfss && ct[i]==0)
        {
            dfs_trn(i);
        }
    }
}