Pagini recente » Cod sursa (job #2984544) | Cod sursa (job #873347) | Rating Encescu Theodor (encescutheodor) | Cod sursa (job #2786491) | Cod sursa (job #1119699)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
const int N = 100005;
const int M = 200005;
int n, m;
int id;
int ord[N], low[N];
bool inStack[N];
stack <int> s;
vector <int> graph[N];
vector <vector <int> > ans;
void read() {
freopen("ctc.in", "r", stdin);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
graph[x].push_back(y);
}
}
vector <int> build_comp(int start) {
vector <int> comp;
int node;
do {
node = s.top();
s.pop();
inStack[node] = false;
comp.push_back(node);
} while (node != start);
return comp;
}
void tarjan(int node) {
ord[node] = low[node] = id;
++id;
s.push(node);
inStack[node] = true;
for (vector <int>::iterator it = graph[node].begin(); it != graph[node].end(); ++it) {
if (ord[*it] == -1) {
tarjan(*it);
low[node] = min(low[node], low[*it]);
} else if (inStack[*it])
low[node] = min(low[node], low[*it]);
}
if (ord[node] == low[node])
ans.push_back(build_comp(node));
}
void print() {
freopen ("ctc.out", "w", stdout);
int nrComp = ans.size();
printf("%d\n", nrComp);
for (int i = 0; i < nrComp; ++i) {
for (int j = 0; j < ans[i].size(); ++j)
printf("%d ", ans[i][j]);
printf("\n");
}
}
int main() {
read();
memset(ord, -1, sizeof(ord));
for (int i = 1; i <= n; ++i)
if (ord[i] == -1)
tarjan(i);
print();
}