Cod sursa(job #2758078)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 8 iunie 2021 15:21:09
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, m, componenta[100001], nr;
bool vizitat_exterior[100001], vizitat_interior[100001];

struct Node
{
    int data;
    Node *next;
}*vecini[100001];

void Adaugare(int nod, int destinatie)
{
    Node *p = new Node;

    p->data = nod;
    p->next = vecini[destinatie];
    vecini[destinatie] = p;
}

void Citire()
{
    ifstream f("ctc.in");

    int nod1, nod2;

    f >> n >> m;

    for(int i = 0; i < m; i++)
    {
        f >> nod1 >> nod2;
        Adaugare(nod1, nod2);
    }
}

void DfsExterior(int varf)
{
    vizitat_exterior[varf] = true;

    for(Node *p = vecini[varf]; p != NULL; p = p->next)
        if(!vizitat_exterior[p->data])
            DfsExterior(p->data);
}

void DfsInterior(int varf)
{
    vizitat_interior[varf] = true;

    for(int i = 1; i <= n; i++)
        if(!vizitat_interior[i])
        {
            for(Node *p = vecini[i]; p != NULL; p = p->next)
                if(p->data == varf)
                    DfsInterior(i);
        }
}

void ResetareViz()
{
    for(int i = 1; i <= n; i++)
    {
        vizitat_exterior[i] = false;
        vizitat_interior[i] = false;
    }
}

void GasireNoduri()
{
    for(int i = 1; i <= n; i++)
        if(vizitat_interior[i] && vizitat_exterior[i])
            componenta[i] = nr;
}

void DeterminareComponenteTareConexe()
{
    for(int i = 1; i <= n; i++)
        if(!componenta[i])
        {
            nr++;
            ResetareViz();
            DfsExterior(i);
            DfsInterior(i);
            GasireNoduri();
        }
}

void Afisare()
{
    ofstream g("ctc.out");

    g << nr << '\n';

    for(int i = 1; i <= nr; i++)
    {
        for(int j = 1; j <= n; j++)
            if(componenta[j] == i)
                g << j << ' ';
        g << '\n';
    }
}

int main()
{
    Citire();
    DeterminareComponenteTareConexe();
    Afisare();

    return 0;
}