Pagini recente » Cod sursa (job #875628) | Cod sursa (job #2071012) | Cod sursa (job #482511) | Cod sursa (job #1579359) | Cod sursa (job #1919180)
#include <iostream>
#include <fstream>
#include <vector>
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int n, m, deep_x, nivmax[NMAX], LONGG[NMAX], NR;
vector <int> G[NMAX], ctc[NMAX];
stack <int> oComponenta;
bool viz[NMAX];
void tarjan (int x) {
++deep_x;
nivmax[x] = deep_x;
LONGG[x] = deep_x;
viz[x] = 1;
oComponenta.push(x);
for (int i = 0; i < G[x].size(); ++i) {
if (!nivmax[G[x][i]]) {
tarjan(G[x][i]);
LONGG[x] = min(LONGG[x], LONGG[G[x][i]]);
}
else
if (viz[G[x][i]]) {
LONGG[x] = min(LONGG[x], LONGG[G[x][i]]);
}
}
if (nivmax[x] == LONGG[x]) {
int vf;
++NR;
do {
vf = oComponenta.top();
oComponenta.pop();
viz[vf] = 0;
ctc[NR].push_back(vf);
}while (vf != x);
}
}
int main ()
{
f>>n>> m;
int x, y;
for (int i = 1; i <= m; ++i) {
f >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= n; ++i) {
if (!nivmax[i]) {
tarjan(i);
}
}
g<<NR<<endl;
for (int i=NR; i>= 1; --i) {
for (int j=ctc[i].size() - 1; j>= 0; --j) {
g <<ctc[i][j] << " ";
}
g << endl;
}
f.close();
g.close();
return 0;
}