Pagini recente » Cod sursa (job #2433302) | Cod sursa (job #2187262) | Cod sursa (job #1242083) | Cod sursa (job #2794837) | Cod sursa (job #2140432)
#include <fstream>
#include <vector>
#include <stack>
#define DEF 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector < int > L[DEF];
vector < vector < int > > SCCs;
stack < int > St;
int n, m, low[DEF], disc[DEF];
bool in_stack[DEF];
void dfs (int u) {
static int time = 0;
disc[u] = low[u] = ++ time;
St.push (u);
in_stack[u] = true;
for (int i = 0; i < L[u].size (); ++ i) {
int v = L[u][i];
if (disc[v] == 0) {
dfs (v);
low[u] = min (low[u], low[v]);
}
else {
if (in_stack[v] == true) {
low[u] = min (low[u], disc[v]);
}
}
}
if (disc[u] == low[u]) {
int w = 0;
vector < int > SCC;
while (w != u) {
w = St.top ();
SCC.push_back (w);
St.pop ();
in_stack[w] = false;
w = St.top ();
}
w = St.top ();
SCC.push_back (w);
in_stack[w] = 0;
St.pop ();
SCCs.push_back (SCC);
}
}
int main () {
fin >> n >> m;
for (int i = 1; i <= m; ++ i) {
int x, y;
fin >> x >> y;
L[x].push_back (y);
}
for (int i = 1; i <= n; ++ i) {
if (disc[i] == 0) {
dfs (i);
}
}
fout << SCCs.size () << '\n';
for (int i = 0; i < SCCs.size (); ++ i) {
for (int j = 0; j < SCCs[i].size (); ++ j) {
fout << SCCs[i][j] << " ";
}
fout << "\n";
}
return 0;
}