Pagini recente » Cod sursa (job #2679734) | Cod sursa (job #1731342) | Cod sursa (job #3184196) | Cod sursa (job #2511673) | Cod sursa (job #954030)
Cod sursa(job #954030)
/*
* Componente tare conexe
* Idee: algoritmul lui Tarjan
*/
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define NMAX 100009
int index = 1, N, cmpIndex = 0;
int dfsIdx[NMAX], lowIdx[NMAX];
stack <int> ctcStack;
vector <int> G[NMAX];
vector <int> components[NMAX];
bool inStack[NMAX];
void dfs (int v)
{
dfsIdx[v] = lowIdx[v] = index++;
ctcStack.push (v);
inStack[v] = true;
for (auto &n : G[v])
if (dfsIdx[n] == 0)
{
dfs (n);
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
}
else if (inStack[n])
{
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
}
if (dfsIdx[v] == lowIdx[v])
{
int n;
do {
n = ctcStack.top();
ctcStack.pop();
inStack[n] = false;
components[cmpIndex].push_back (n);
} while (n != v);
cmpIndex++;
}
}
int main()
{
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int m;
fin >> N >> m;
for (; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back (y);
}
for (int v = 1; v <= N; ++v)
if (!dfsIdx[v])
{
dfs (v);
}
fout << cmpIndex << endl;
for (size_t c = 0; c < cmpIndex; ++c)
{
for (auto &v : components[c])
fout << v << ' ';
fout << endl;
}
fin.close();
fout.close();
return EXIT_SUCCESS;
}