Pagini recente » Cod sursa (job #1410943) | Cod sursa (job #2829352) | Rating cocos florin (cocosflorin) | Cod sursa (job #1732750) | Cod sursa (job #954024)
Cod sursa(job #954024)
/*
* 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;
int dfsIdx[NMAX], lowIdx[NMAX];
stack <int> ctcStack;
vector <int> G[NMAX];
vector <vector <int>> components;
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;
components.push_back (vector <int>());
do {
n = ctcStack.top();
ctcStack.pop();
inStack[n] = false;
components.back().push_back (n);
} while (n != v);
}
}
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 << components.size() << endl;
for (auto &component : components)
{
for (auto &v : component)
fout << v << ' ';
fout << endl;
}
fin.close();
fout.close();
return EXIT_SUCCESS;
}