# PBinfo #3365 – DigrafulCTC – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se dă un digraf (graf orientat) cu n noduri numerotate de la 1 la n. Graful componentelor tare conexe se obține astfel: se construiesc componentele tare conexe, apoi fiecare astfel de componentă devine nod în noul graf. Apoi din lista inițială de arce se păstrează în noul graf numai arcele care au extremitățile în componente tare conexe diferite. Dacă există mai multe arce între aceleași două noduri în noul digraf, se păstrează toate.

Componentele tare conexe se vor construi astfel: prima componentă este cea care conține nodul 1, a doua componentă este cea care conține cel mai mic nod care nu se află în prima componentă ș.a.m.d. 

Lista de adiacență asociată unui nod i din digraful componentelor tare conexe conține toate nodurile j cu proprietatea că există arcul (i, j).

Cerința
Să se afișeze listele de adiacență asociate noului digraf.

Date de intrare
Programul citește de la tastatură numerele n și m, iar apoi m perechi de forma i j cu semnificația: există arcul (i,j) în digraf.

Date de ieșire
Programul va afișa pe ecran nrC linii, unde nrC este numărul componentelor tari conexe, adică numărul de noduri din noul graf. Pe fiecare din următoarele i linii se vor afișa, în ordine crescătoare adiacenții externi ai nodului i din noul digraf. Dacă există k arce (i, j) atunci în lista de adiacență a lui i nodul j va apărea de k ori, deci se va afișa de k ori. Dacă un nod k din noul digraf are gradul exterior 0, se va afișa doar un 0.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ m ≤ 200.000
în toate testele, digraful are cel puțin două componente tari conexe

Exemplu:
Intrare

8 10
1 2
2 3
3 1
4 5
5 6
6 7
7 4
6 4
4 1
4 8
Ieșire

0
1 3
0
Explicație
Graful are 8 noduri și 10 arce:



Prima componentă conexă este formată cu nodurile 1 2 3, a doua cu nodurile 4 5 6 7, iar a treia este formată din nodul 8. Din digraful inițial se păstrează numai arcele (4,1) și (4,8). Graful asociat componentelor tare conexe este:

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define nmax 100003
using namespace std;
vector<int> G[nmax]; /// listele de ad. ale noului digraf
vector<int> L[nmax]; /// listele digrafului initial
vector<int> H[nmax]; /// listele digrafului transpus
bool viz[nmax];
int ctc[nmax]; /// ctc[i]=j : nodul i e in componenta j
int n, m, nrc;
int v[nmax], k, t[nmax];
int X[2 * nmax], Y[2 * nmax]; /// memoreaza arcele initiale
void Citire()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> X[i] >> Y[i];
        L[X[i]].push_back(Y[i]);
        H[Y[i]].push_back(X[i]);
    }
}
void DFS1(int nod)
{
    viz[nod] = true;
    for (auto i : L[nod])
        if (!viz[i]) DFS1(i);
    v[++k] = nod;
}
void DFS2(int nod)
{
    viz[nod] = false;
    for (auto i : H[nod])
        if (viz[i]) DFS2(i);
    ctc[nod] = nrc;
}
void Kosaraju()
{
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            DFS1(i);
    for (int i = n; i >= 1; i--)
        if (viz[v[i]])
        {
            nrc++;
            DFS2(v[i]);
        }
}
/// constructie digraf nou si afisare liste de adiacenta
void DigrafNou()
{
    int i, x = 0;
    for (i = 1; i <= n; i++)
        if (t[ctc[i]] == 0)
            t[ctc[i]] = ++x;
    for (i = 1; i <= n; i++)
        ctc[i] = t[ctc[i]];
    for (i = 1; i <= m; i++)
        if (ctc[X[i]] != ctc[Y[i]])
            G[ctc[X[i]]].push_back(ctc[Y[i]]);
    for (i = 1; i <= nrc; i++)
        if (G[i].size() > 0)
            sort(G[i].begin(), G[i].end());
    for (i = 1; i <= nrc; i++)
        if (G[i].size() == 0) cout << "0\n";
        else
        {
            for (auto j : G[i])
                cout << j << " ";
            cout << "\n";
        }
}
int main()
{
    Citire();
    Kosaraju();
    DigrafNou();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3365)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3365/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3365/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)