Cod sursa(job #3202050)

Utilizator nicholas9onicaMike Krack nicholas9onica Data 10 februarie 2024 15:06:24
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>>graph;
vector<vector<int>>graphinv;
vector<int>ord, comp;
vector<bool> vizitat1;
vector<bool> vizitat2;
vector<vector<int>> rasp;
void dfs1(int nod)
{
    vizitat1[nod]=1;
    for(int vecin: graph[nod])
    {
        if(vizitat1[vecin]==0)
        {
            dfs1(vecin);
        }
    }
    ord.push_back(nod);
}
void dfs2 (int nod)
{
    vizitat2[nod]=1;
    for(int vecin: graphinv[nod])
    {
        if(!vizitat2[vecin])
        {
            dfs2(vecin);
        }
    }
    comp.push_back(nod);
}
int main()
{
    int n,m,x,y,nrctc=0;
    fin>>n>>m;
    graph.resize(n+1);
    graphinv.resize(n+1);
    vizitat1.resize(n+1);
    vizitat2.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        graph[x].push_back(y);
        graphinv[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
    {
        if(vizitat1[i]==0)
            dfs1(i);
    }
    while(!ord.empty())
    {
        int nod=ord.back();
        ord.pop_back();
        if (vizitat2[nod]) {
            continue;
        }
        nrctc++;
        dfs2(nod);
        rasp.push_back(comp);
        comp.clear();
    }
    fout<<nrctc<<"\n";
    for(int i=0; i<nrctc; i++)
    {
        for(int elem: rasp[i])
        {
            fout<<elem<<" ";
        }
        fout<<"\n";
    }

}