Pagini recente » Cod sursa (job #389849) | Cod sursa (job #1578839) | Cod sursa (job #1544846) | Cod sursa (job #1537528) | Cod sursa (job #1917177)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#define NMAX 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, indecs, ind[NMAX], lowlink[NMAX], comps;
vector <int> g[NMAX], ctc[NMAX];
stack <int> steve;
bitset <NMAX> inst;
void tarjan (int node) {
++indecs;
ind[node] = indecs;
lowlink[node] = indecs;
//cout << node << " ";
inst[node] = 1;
steve.push(node);
for (int i = 0; i < g[node].size(); ++i) {
if (!ind[g[node][i]]) {
tarjan(g[node][i]);
lowlink[node] = min(lowlink[node], lowlink[g[node][i]]);
}
else
if (inst[g[node][i]]) {
lowlink[node] = min(lowlink[node], lowlink[g[node][i]]);
}
}
if (ind[node] == lowlink[node]) {
int x;
++comps;
do {
x = steve.top();
steve.pop();
inst[x] = 0;
ctc[comps].push_back(x);
}while (x != node);
}
}
int main ()
{
fin >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!ind[i]) {
tarjan(i);
}
}
fout << comps << '\n';
for (int i = comps; i >= 1; --i) {
for (int j = ctc[i].size() - 1; j >= 0 ; --j) {
fout << ctc[i][j] << " ";
}
fout << '\n';
}
/*while (steve.size()) {
cout << steve.top() << " ";
steve.pop();
}*/
fin.close();
fout.close();
return 0;
}