Pagini recente » Cod sursa (job #652925) | Cod sursa (job #1831352) | Cod sursa (job #3126303) | Cod sursa (job #1375412) | Cod sursa (job #2122435)
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
using namespace std;
const int NMAX = 100005;
vector<int> g[NMAX];
vector<vector<int>> comp;
stack<int> st;
bitset<NMAX> v;
int n, m;
int index[NMAX], lowlink[NMAX];
int globalIndex;
void read() {
scanf("%d %d ", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d ", &x, &y);
g[x].push_back(y);
}
}
void dfs(int x) {
index[x] = lowlink[x] = ++globalIndex;
st.push(x);
v[x] = 1;
for (int y : g[x]) {
if (!index[y]) {
dfs(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
} else if (v[y]) {
lowlink[x] = min(lowlink[x], index[y]);
}
}
if (index[x] == lowlink[x]) {
vector<int> c;
int y;
do {
y = st.top();
st.pop();
v[y] = 0;
c.push_back(y);
} while (y != x);
comp.push_back(c);
}
}
void tarjan() {
for (int i = 1; i <= n; i++)
if (!index[i])
dfs(i);
}
void print() {
printf("%d\n", comp.size());
for (auto c : comp) {
for (int x : c)
printf("%d ", x);
printf("\n");
}
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
tarjan();
print();
return 0;
}