Pagini recente » Cod sursa (job #2308555) | Cod sursa (job #1243759) | Cod sursa (job #2829436) | Simulare 26 | Cod sursa (job #2402073)
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> L[100002];
vector <int> G[100002];
vector < vector <int> > CTC_solution;
stack <int> stiva;
vector <int> componenta;
bool viz1[100002];
bool viz2[100002];
int n, m;
/// Eu trebuie sa scot
void Citire()
{
int i, j;
int x, y;
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
G[y].push_back(x);
}
}
void DFS_1(int k)
{
int j, nod;
viz1[k] = 1;
for (j = 0; j < L[k].size(); j++)
{
nod = L[k][j];
if (!viz1[nod])
DFS_1(nod);
}
stiva.push(k);
}
void DFS_2(int k)
{
int j, nod;
viz2[k] = 1;
cout << k << endl;
for (j = 0; j < G[k].size(); j++)
{
nod = G[k][j];
if (!viz2[nod])
DFS_2(nod);
}
componenta.push_back(k);
}
void Rezolva()
{
int i, j, nod;
for (i = 1; i <= n; i++)
if (!viz1[i])
DFS_1(i);
while (!stiva.empty())
{
componenta.clear();
nod = stiva.top();
stiva.pop();
if (!viz2[nod])
{
DFS_2(nod);
CTC_solution.push_back(componenta);
}
}
}
void Afisare()
{
/// cout << "Im here mofackeeeeers";
int i, j;
fout << CTC_solution.size() << "\n";
for (i = 0; i < CTC_solution.size(); i++)
{
for (j = 0; j < CTC_solution[i].size()-1; j++)
{
fout << CTC_solution[i][j] << " ";
}
fout << CTC_solution[i][CTC_solution[i].size()-1];
fout << "\n";
}
}
int main ()
{
int i;
Citire();
Rezolva();
Afisare();
return 0;
}