Cod sursa(job #2783182)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 13 octombrie 2021 22:24:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
/*
Componente tare conexe
Se dă un graf orientat G = (V, E). O componentă tare conexă a grafului orientat G este o mulţime maximală de vârfuri U inclusă în V, astfel încât, pentru fiecare pereche de vârfuri u şi v din U avem atât drum de la u la v cât şi drum de la v la u. Cu alte cuvinte, vâfurile u şi v sunt accesibile unul din celălalt.

Cerinţă
Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.

Date de intrare
Fişierul de intrare ctc.in conţine pe prima linie două numere naturale N si M ce reprezintă numărul de noduri din G şi numărul muchiilor. Pe următoarele M linii se vor afla câte două numere naturale x şi y, separate prin spaţiu, reprezentând muchia orientată (x, y).

Date de ieşire
În fişierul de ieşire ctc.out se va afişa pe prima linie un singur număr reprezentând numărul componentelor tare conexe. Pe fiecare din următoarele linii se va scrie câte o componentă tare conexă prin enumerarea nodurilor componente. Acestea pot fi afişate în orice ordine.

Restricţii
1 ≤ N ≤ 100 000
1 ≤ M ≤ 200 000
Pentru 30% din teste, 1 ≤ N ≤ 100 si 1 ≤ M ≤ 500
Pentru 60% din teste, 1 ≤ N ≤ 5 000 si 1 ≤ M ≤ 25 000
Pentru aflarea corectă doar a numărului componentelor tare conexe se va acorda 40% din punctaj
*/
// Algoritmul lui Kosaraju
#include <bits/stdc++.h>
#define pb push_back
#define NMAX 100005

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

stack < int > s;
vector < int > v1[NMAX], v2[NMAX], r[NMAX];
bitset < NMAX > viz1, viz2;
int nr;

void dfs1(int k);
void dfs2(int k);

int main()
{
    ios_base::sync_with_stdio(false);
    int n, m, x, y, i;

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        v1[x].pb(y);
        v2[y].pb(x);
    }

    for(i = 1; i <= n; i++) if(viz1[i] == 0) dfs1(i);

    while(s.empty() == 0)
    {
        x = s.top();
        s.pop();

        if(viz2[x] == 0) nr++, dfs2(x);
    }

    fout << nr << '\n';
    for(i = 1; i <= nr; i++)
    {
        for(auto it:r[i]) fout << it << ' ';
        fout << '\n';
    }

    return 0;
}

void dfs1(int k)
{
    viz1[k] = 1;
    for(auto it:v1[k]) if(viz1[it] == 0) dfs1(it);
    s.push(k);
}

void dfs2(int k)
{
    viz2[k] = 1;
    for(auto it:v2[k]) if(viz2[it] == 0) dfs2(it);
    r[nr].pb(k);
}

/*
IN:
8 12
1 2
2 6
6 7
7 6
3 1
3 4
2 3
4 5
5 4
6 5
5 8
8 7

OUT:
2
1 2 3
4 5 6 7 8
*/