Cod sursa(job #3226906)

Utilizator AlexMihAlexandru Mihailescu AlexMih Data 23 aprilie 2024 11:41:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <iostream>
#include <vector>


using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> G[100001],GT[100001],ctc[100001];
vector<int> S;
bool viz[100001];
int n,m,nrc;

void dfs(int nod)
{
    int i;
    viz[nod] = true;
    for(i = 0; i < G[nod].size(); i++)
    {
        int nod_next = G[nod][i];
        if(viz[nod_next] == false)
            dfs(nod_next);
    }
    S.push_back(nod);
}

void tdfs(int nod)
{
    int i;
    viz[nod] = true;
    ctc[nrc].push_back(nod);
    for(i = 0; i < GT[nod].size(); i++)
    {
        int nod_next = GT[nod][i];
        if(viz[nod_next] == false)
            tdfs(nod_next);
    }
}

int main()
{  
    int i,a,b;
    f>>n>>m;
    nrc = 0;
    for(i = 1; i <= m; i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    for(i = 1; i <= n; i++)
    {
        if(viz[i] == false)
            dfs(i);
    }
    for(i = 1; i <= n; i++)
    {
        viz[i] = false;
    }
    for(i = S.size()-1; i >= 0; i--)
    {
        int nod = S[i];
        if(viz[nod] == false)
        {
            nrc++;
            tdfs(nod);
        }
    }
    g<<nrc<<'\n';
    for(i = 1; i <= nrc; i++)
    {
        for(int j = 0; j < ctc[i].size(); j++)
        {
            g<<ctc[i][j]<<" ";
        }
        g<<'\n';
    }
    return 0;

}