Cod sursa(job #1906843)

Utilizator jurjstyleJurj Andrei jurjstyle Data 6 martie 2017 16:39:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <list>
#include <algorithm>
#include <set>


using namespace std ;

ifstream f("retele.in") ;
ofstream g("retele.out") ;

const int Nmax = 50001 ;

vector <int> G[Nmax];
vector <int> Viz, Nivel, Length;
stack <int> St;
int n, m, current_node, nv;
set <set <int>> Sol;
set <int> Sol_curent;

void read()
{
    f >> n >> m;
    for (int cnt = 1; cnt <= m; ++cnt)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
    }
}
void DFS(int x)
{
    Viz[x] = true;
    St.push(x);
    Nivel[x] = Length[x] = ++nv;
    for (const int & y : G[x])
        if (Nivel[y] == 0) //daca e muchie de arbore
        {
            DFS(y);
            Length[x] = min(Length[x], Length[y]);
        }
        else if (Viz[y] == true)//daca e muchie de intoarcere
            Length[x] = min(Length[x], Nivel[y]);
    if (Nivel[x] == Length[x])
    {
        Sol_curent.clear();
        while (true)
        {
            int nod_curent = St.top();
            Sol_curent.insert(nod_curent);
            Viz[nod_curent] = false;
            St.pop();
            if (x == nod_curent)
                break;
        }
        Sol.insert(Sol_curent);
    }
}
int main ()
{
    read () ;
    Viz = Nivel = Length = vector <int> (n + 1);
    int cnt_comp_tare_conexe = 0 ;
    for (int i = 1; i <= n; ++i)
        if (Nivel[i] == 0)
        {
            ++cnt_comp_tare_conexe;
            DFS(i);
        }
    g << cnt_comp_tare_conexe << '\n' ;
    for (const set <int> & x : Sol)
        if (!x.empty())
            {
             g << x.size () << " " ;
             for ( const int & y : x )
                g << y << " " ;
             g << "\n" ;
            }
}