Pagini recente » Cod sursa (job #673844) | Cod sursa (job #836764) | Cod sursa (job #2022258) | Cod sursa (job #1359976) | Cod sursa (job #1686048)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <map>
#include <bitset>
#include <stack>
#define NMAX 100009
using namespace std;
int N, M, order, found[NMAX], low[NMAX];
vector<int> G[NMAX];
map <string, int> string2int;
map <int, string> int2string;
vector< vector<int> > ctc;
stack<int> st;
bitset<NMAX> inStack;
void tarjan(int node) {
found[ node ] = low[ node ] = ++order;
st.push(node);
inStack[ node ] = 1;
for (auto it = G[node].begin(); it != G[node].end(); ++it) {
if (!found[ *it ]) {
tarjan(*it);
low[ node ] = min(low[ node ], low[ *it ]);
} else {
if (inStack[ *it ]) {
low[ node ] = min(low[ node ], found[ *it ]);
}
}
}
if (found[ node ] == low[ node ]) {
vector< int > tmp;
int current = -1;
while (!st.empty() && current != node) {
tmp.push_back( current = st.top() );
st.pop();
inStack[ current ] = 0;
}
ctc.push_back(tmp);
}
}
void ctcTarjan() {
order = 0;
inStack.reset();
for (int i = 1; i <= N; ++i) {
if (!found[ i ]) {
tarjan(i);
}
}
}
void printCTC() {
printf("%d\n", (int) ctc.size());
for (auto it = ctc.begin(); it != ctc.end(); ++it) {
for (auto node = it->begin(); node != it->end(); ++node) {
printf("%d ", *node);
}
printf("\n");
}
}
void read() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
ctcTarjan();
printCTC();
return 0;
}