Pagini recente » Cod sursa (job #1750764) | Cod sursa (job #1992331) | Cod sursa (job #2294543) | Cod sursa (job #1058495) | Cod sursa (job #3002783)
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100000 + 5;
int n, m, nr_componente;
vector<int> G[NMAX], G_transpus[NMAX], componente[NMAX];
stack<int> noduri_procesate;
bool vizitat[NMAX];
void firstDFS(int nod)
{
vizitat[nod] = true;
for (int i = 0; i < G[nod].size(); i++)
{
int vecin = G[nod][i];
if (!vizitat[vecin])
firstDFS(vecin);
}
noduri_procesate.push(nod);
}
void secondDFS(int nod)
{
vizitat[nod] = true;
componente[nr_componente].push_back(nod);
for (int i = 0; i < G_transpus[nod].size(); i++)
{
int vecin = G_transpus[nod][i];
if (!vizitat[vecin])
secondDFS(vecin);
}
}
// Algoritmul lui Kosaraju
int main()
{
fin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G_transpus[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!vizitat[i])
firstDFS(i);
memset(vizitat, 0, sizeof vizitat);
while (!noduri_procesate.empty())
{
int nod = noduri_procesate.top();
if (!vizitat[nod])
{
nr_componente++;
secondDFS(nod);
}
noduri_procesate.pop();
}
fout << nr_componente << "\n";
for (int i = 1; i <= nr_componente; i++)
{
for (int j = 0; j < componente[i].size(); j++)
fout << componente[i][j] << " ";
fout << "\n";
}
return 0;
}