Cod sursa(job #3270925)

Utilizator TeoRoGaming_YgVoinea Ionut-Florin TeoRoGaming_Yg Data 24 ianuarie 2025 21:02:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> v1[100001], v2[100001], ctc[100001];
int verif[100001];
int st[100001];
int cnt, cnt2;

void dfs1(int nod)
{
    verif[nod] = 1;
    for(auto y:v1[nod])
    {
        if(verif[y] == 0) dfs1(y); ///mergem recursiv prin nodurile nevizitate
    }
    st[cnt] = nod;
    cnt++;
}

void dfs2(int nod)
{
    verif[nod] = 1;
    ctc[cnt2].push_back(nod);
    for(auto y:v2[nod])
    {
        if(verif[y] == 0) dfs2(y);
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        f >> a >> b;
        v1[a].push_back(b);
        v2[b].push_back(a);
    }
    for(int i = 1; i <= n; i ++)
        {
            if(verif[i] == 0) dfs1(i);
        }

    for(int i = 1; i <= n; i ++)
        verif[i] = 0;

    for(int i = cnt - 1; i >= 0; i --)
    {
        int x = st[i];
        if(verif[x] == 0)
        {
            dfs2(x);
            cnt2 ++;
        }
    }
    g << cnt2 << '\n';
    for(int i = 0; i < cnt; i ++)
    {
        for(auto it : ctc[i])
            g << it << " ";
        g << '\n';
    }
    return 0;
}