Cod sursa(job #2901955)

Utilizator roberttrutaTruta Robert roberttruta Data 14 mai 2022 22:12:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
//tarjan

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define pauza 9999999

vector <int> v[100005];
int viz[100005], low[100005], lv[100005], stiva[100005], afis[200005];
int t, nr_comp, nr, level;

void dfs(int start)
{
    viz[start] = 2;
    low[start] = level;
    lv[start] = level;
    t++;
    stiva[t] = start;
    for(int i=0; i<v[start].size(); i++)
    {
        int vecin = v[start][i];
        if(viz[vecin] == 0)
        {
            level++;
            dfs(vecin);
        }
        if(viz[vecin] == 2)
            low[start] = min(low[start], low[vecin]);
    }
    if(lv[start] == low[start])
    {
        nr_comp++;
        do
        {
            viz[stiva[t]] = 1;
            nr++;
            afis[nr] = stiva[t];
            t--;
        }while(stiva[t+1] != start);
        nr++;
        afis[nr] = pauza;
    }
}

int main()
{
    int n,m,i,a,b;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b;
        v[a].push_back(b);
    }
    for(i=1; i<=n; i++)
        if(viz[i] == 0)
            dfs(i);

    g<<nr_comp<<'\n';
    nr = 1;
    for(i=1; i<=nr_comp; i++)
    {
        while(afis[nr] != pauza)
        {
             g<<afis[nr]<<' ';
             nr++;
        }
        g<<'\n';
        nr++;
    }

    return 0;
}