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

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:

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema DigrafulCTC:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3365 DigrafulCTC

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3365 DigrafulCTC de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3365 DigrafulCTC