Cod sursa(job #3286762)

Utilizator TudorNMnegoita tudor mihai TudorNM Data 14 martie 2025 17:13:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
#define NMAX 100001

using namespace std;

vector <int> aux;
vector <vector<int>> ctc;
vector <vector<int>> a(NMAX);
vector <vector<int>> ar(NMAX);
vector <int> ord;
int rez=0;
vector <int>frecv(NMAX);
vector <int>frecv0(NMAX);
void dfs1(int nod)
{    frecv[nod]=1;

    for(int i=0; i<a[nod].size(); i++)
    {
        if(frecv[a[nod][i]]==0)
        {
            frecv[a[nod][i]]=1;
            dfs1(a[nod][i]);
        }
    }
    ord.push_back(nod);
}

void dfs2(int nod)
{

    for(int j=0; j<ar[nod].size(); j++)
    {
        if(frecv0[ar[nod][j]]==0)
        {
            frecv0[ar[nod][j]]=1;
            dfs2(ar[nod][j]);
        }
    }

    aux.push_back(nod);
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int main()
{
    int n,m;
    fin>>n>>m;
    for(int u,v,i=1; i<=m; i++)
    {
        fin>>u>>v;
        a[u].push_back(v);
        ar[v].push_back(u);
    }
    for (int i=1; i<=n; i++)
    {
        if(frecv[i]==1)
            continue;
        frecv[i]=1;
        dfs1(i);
    }

    frecv.clear();

    for(int i=ord.size()-1; i>=0; i--)
    {
        if(frecv0[ord[i]]==1)
            continue;
        frecv0[ord[i]]=1;
        dfs2(ord[i]);
        rez++;
        ctc.push_back(aux);
        aux.clear();
    }
    rez--;
    fout<<rez+1<<'\n';
    for(int i=0; i<=rez; i++)
    {
        for(int j=0; j<ctc[i].size(); j++)
        {
            fout<<ctc[i][j]<<" ";
        }
        fout<<'\n';
    }
    return 0;
}