Pagini recente » Cod sursa (job #491091) | Cod sursa (job #1134725) | Cod sursa (job #2011676) | Cod sursa (job #774530) | Cod sursa (job #2144553)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100005
vector<int> adj[NMAX];
int lowlink[NMAX];
int idx[NMAX];
bitset<NMAX> in_stack;
vector<int> component;
vector<vector<int>> sol;
stack<int> S;
int indecs;
int n, m;
void tarjan(int node) {
idx[node] = lowlink[node] = indecs++;
S.push(node);
in_stack[node] = true;
for (auto &next_node: adj[node]) {
if (idx[next_node] == -1) {
tarjan(next_node);
lowlink[node] = min(lowlink[node], lowlink[next_node]);
} else if (in_stack[next_node]) {
lowlink[node] = min(lowlink[node], lowlink[next_node]);
}
}
if (idx[node] == lowlink[node]) {
component.clear();
int another_node;
do {
component.push_back(another_node = S.top());
S.pop();
in_stack[another_node] = 0;
} while (another_node != node);
sol.push_back(component);
}
}
int main() {
freopen("carici.in", "r", stdin);
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d",&n, &m);
int x, y;
for (int i = 0 ; i < m ;i++) {
scanf("%d%d", &x, &y);
adj[x].push_back(y);
}
for (int i = 1; i <= n; i++)
idx[i] = -1;
for (int i = 1; i <= n; i++)
if (idx[i] == -1) tarjan(i);
cout << sol.size() << "\n";
for (auto &s: sol) {
sort(s.begin(), s.end());
for (auto &i: s) {
cout << i << " ";
} cout << "\n";
}
return 0;
}