Pagini recente » Cod sursa (job #2172609) | Cod sursa (job #2929487) | Cod sursa (job #2142151) | Cod sursa (job #1717189) | Cod sursa (job #2357921)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define pb push_back
using namespace std;
const int MAXN = 100010;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, ind[MAXN], link[MAXN], nr, compNr;
bool inStack[MAXN];
vector<int> edges[MAXN], comp[MAXN];
stack<int> s;
void read() {
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
edges[x].pb(y);
}
}
inline int doMin(int a, int b) {
return (a < b ? a : b);
}
void doDfs(int vertix) {
s.push(vertix);
inStack[vertix] = true;
link[vertix] = ind[vertix] = ++nr;
for (auto &it: edges[vertix]) {
if (!ind[it]) {
doDfs(it);
link[vertix] = doMin(link[it], link[vertix]);
}
else if (inStack[it] == true) {
link[vertix] = doMin(ind[it], link[vertix]);
}
}
if (link[vertix] == ind[vertix]) {
compNr++;
while(!s.empty()) {
int top = s.top();
s.pop();
inStack[top] = false;
comp[compNr].pb(top);
if (top == vertix) {
break;
}
}
}
}
void solve() {
for (int i = 1; i <= n; ++i) {
if (!ind[i])
doDfs(i);
}
}
void print() {
fout << compNr << "\n";
for (int i = 1; i <= compNr; ++i) {
for (auto &it: comp[i]) {
fout << it << " ";
}
fout << "\n";
}
}
int main() {
read();
solve();
print();
return 0;
}