Pagini recente » Cod sursa (job #1604778) | Cod sursa (job #1265695) | Cod sursa (job #97357) | Cod sursa (job #2070456) | Cod sursa (job #3268939)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 1e5;
int N, M;
vector<int> G[MAXN + 1];
bool viz[MAXN + 1], inTStack[MAXN + 1];
stack<int> tStack;
vector<vector<int>> ctc;
int gIdx = 0;
int ll[MAXN + 1], idx[MAXN + 1];
void tarjan(int nod) {
tStack.push(nod);
inTStack[nod] = 1;
viz[nod] = 1;
idx[nod] = ll[nod] = ++gIdx;
for (const auto& n : G[nod]) {
if (!viz[n]) {
tarjan(n);
ll[nod] = min(ll[nod], ll[n]);
} else if (inTStack[n]) {
ll[nod] = min(ll[nod], idx[n]);
}
}
if (ll[nod] == idx[nod]) {
vector<int> comp;
comp.push_back(nod);
while (tStack.top() != nod) {
comp.push_back(tStack.top());
inTStack[tStack.top()] = 0;
tStack.pop();
}
tStack.pop();
ctc.push_back(comp);
}
}
int main() {
fin >> N >> M;
int a, b;
while (M--) {
fin >> a >> b;
G[a].push_back(b);
}
for (int i = 1; i <= N; i++) {
if (!viz[i])
tarjan(i);
while (!tStack.empty()) {
vector<int> comp;
comp.push_back(tStack.top());
tStack.pop();
ctc.push_back(comp);
}
}
fout << ctc.size() << '\n';
for (const auto& comp : ctc) {
for (const auto& n : comp)
fout << n << ' ';
fout << '\n';
}
return 0;
}