Pagini recente » Cod sursa (job #915279) | Borderou de evaluare (job #119123) | Borderou de evaluare (job #833337) | Cod sursa (job #1755905) | Cod sursa (job #2981402)
#include <cstdio>
#include <vector>
#include <memory>
#include <stack>
using namespace std;
class Solver{
private:
stack<int> kosarajuStack;
vector<bool> used;
void DFS(const vector<vector<int>>& Graph, int k) {
used[k] = true;
for (auto v: Graph[k])
if (!used[v])
DFS(Graph, v);
kosarajuStack.emplace(k);
}
void DFST(const vector<vector<int>>& GraphT, int k, vector<int>& ctc) {
used[k] = true;
for (auto v: GraphT[k])
if (!used[v])
DFST(GraphT, v, ctc);
ctc.emplace_back(k);
}
vector<vector<int>> kosaraju(const vector<vector<int>>& Graph) {
vector<vector<int>> GraphT((int)Graph.size());
for (int curNode = 0; curNode < (int)Graph.size(); ++curNode)
for (auto v: Graph[curNode])
GraphT[v].emplace_back(curNode);
used.resize((int)Graph.size());
for (int i = 0; i < (int)Graph.size(); ++i)
if (!used[i])
DFS(Graph, i);
fill(used.begin(), used.end(), false);
vector<vector<int>> ctcs;
int k = -1;
while (!kosarajuStack.empty()) {
k = kosarajuStack.top();
kosarajuStack.pop();
if (used[k])
continue;
vector<int> ctc;
DFST(GraphT, k, ctc);
ctcs.emplace_back(ctc);
}
return ctcs;
}
public:
Solver() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
}
~Solver() {
fclose(stdin);
fclose(stdout);
}
void execute() {
int N, M;
scanf("%d%d", &N, &M);
vector<vector<int>> Graph(N);
int from, to;
for (int i = 0; i < M; ++i) {
scanf("%d%d", &from, &to);
--from; --to;
Graph[from].emplace_back(to);
}
vector<vector<int>> ctcs = kosaraju(Graph);
printf("%d\n", (int)ctcs.size());
for (auto ctc: ctcs) {
for (auto v: ctc)
printf("%d ", v + 1);
printf("\n");
}
}
};
int main() {
unique_ptr<Solver> s = make_unique<Solver>();
s->execute();
return 0;
}