Pagini recente » Cod sursa (job #1090464) | Cod sursa (job #2543005) | Rating Gontariu Andreea Cristina (andreeacristina) | Cod sursa (job #1870636) | Cod sursa (job #1906843)
#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" ;
}
}