Cod sursa(job #2930076)

Utilizator VladTalpigaVlad Talpiga VladTalpiga Data 27 octombrie 2022 14:21:14
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
//Folosim algoritmul lui Koseraju (2dfs): O(n+m)

#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

int n, m, nrcomp = 0;
stack <int> s;
vector <vector<int>> graf(100001), transpus(100001), ctc;
vector <bool> vizitat(100001, false);

void dfs1(int nod)
{
    vizitat[nod] = true;

    for(auto vecin : graf[nod])
    {
        if(!vizitat[vecin])
            dfs1(vecin);
    }

    s.push(nod);
}

void dfs2(int nod)
{
    vizitat[nod] = true;

    for(auto vecin : graf[nod])
    {
        if(!vizitat[vecin])
            dfs2(vecin);
    }

    ctc[nrcomp].push_back(nod);
}



int main()
{
    int a, b, i;

    f >> n >> m;

    graf.resize(n+1);
    transpus.resize(n+1);
    vizitat.resize(n+1);

    for(i = 1; i <= m; i++)
    {
        f >> a >> b;
        graf[a].push_back(b);
        transpus[b].push_back(a);
    }

    for(i = 1; i <= nrcomp; i++)
    {
        if(!vizitat[i])
            dfs1(i);
    }

    for(i = 1; i <= n; i++)
        vizitat[i] = false;

    while(!s.empty())
    {
        int nod = s.top();
        s.pop();

        if(!vizitat[nod])
        {
            nrcomp++;
            dfs2(i);
        }
    }

    g << nrcomp << '\n';

    for(i = 1; i <= nrcomp; i++)
    {
        for(auto nod : ctc[i])
            g << nod << ' ';
        g << '\n';
    }

    return 0;
}