Pagini recente » Cod sursa (job #720240) | Cod sursa (job #2832641) | Cod sursa (job #1359425) | Cod sursa (job #556259) | Cod sursa (job #3268938)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 1e5;
vector<int> G[MAXN + 1], Gt[MAXN + 1];
stack<int> kStack;
bitset<MAXN + 1> viz;
int N, M;
void dfs(int nod) {
viz[nod] = 1;
for (const auto& x : G[nod])
if (!viz[x])
dfs(x);
kStack.push(nod);
}
vector<vector<int>> ctc;
vector<int> comp;
void dfst(int nod) {
viz[nod] = 1;
for (const auto& x : Gt[nod]) {
if (!viz[x])
dfst(x);
}
comp.push_back(nod);
}
int main() {
fin >> N >> M;
int a, b;
while (M--) {
fin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for (int i = 1; i <= N; i++) {
if (!viz[i])
dfs(i);
}
viz.reset();
while (!kStack.empty()) {
if (!viz[kStack.top()]) {
comp = vector<int>();
dfst(kStack.top());
ctc.push_back(comp);
}
kStack.pop();
}
fout << ctc.size() << '\n';
for (const auto& c : ctc) {
for (const auto& x : c)
fout << x << ' ';
fout << '\n';
}
return 0;
}