Pagini recente » Cod sursa (job #2944691) | Cod sursa (job #2849711) | Cod sursa (job #1127499) | Cod sursa (job #3145142) | Cod sursa (job #2209299)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <list>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100002;
int N, M;
vector <int> G[NMAX];
stack <int> St;
vector <bool> Viz;
vector <int> Nivel, Length, Comp_curent;
vector <vector <int>> Cc;
int nv;
void DFS(int);
int main()
{
f >> N >> M;
Viz = vector <bool> (N + 1, 0);
Nivel = Length = vector <int> (N + 1, 0);
for (int i = 1; i <= M; ++i)
{
int x, y;
f >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= N; ++i)
if (Nivel[i] == 0)
DFS(i);
g << Cc.size() << "\n";
for (int i = 0; i < Cc.size(); ++i)
{
for (const int & j : Cc[i])
g << j << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}
void DFS(int x)
{
Viz[x] = true;
St.push(x);
Nivel[x] = Length[x] = ++nv;
for (const int & y : G[x])
if (Viz[y] == false) //daca e muchie de arbore
{
DFS(y);
Length[x] = min(Length[x], Length[y]);
}
else //daca e muchie de intoarcere
Length[x] = min(Length[x], Nivel[y]);
if (Nivel[x] == Length[x])
{
Comp_curent.clear();
while (true)
{
int nod_curent = St.top();
Comp_curent.push_back(nod_curent);
Viz[nod_curent] = false;
St.pop();
if (x == nod_curent)
break;
}
Cc.push_back(Comp_curent);
}
}