Pagini recente » Cod sursa (job #841499) | Cod sursa (job #573911) | Cod sursa (job #2864750) | Cod sursa (job #3251986) | Cod sursa (job #2251020)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <functional>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "ctc";
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define USE_FILES
#ifdef USE_FILES
#define cin fin
#define cout fout
#endif
using graph_t = std::vector< std::vector<int> >;
class TarjanSccs {
public:
std::vector< std::vector<int> >&& computeSccs(const graph_t& graph) {
init(graph);
buildSccs();
return std::move(_sccs);
}
private:
const int UNVISITED_INDEX = 0;
const int FIRST_INDEX = 1;
void init(const graph_t& graph) {
_graph = &graph;
_inStack.resize(graph.size());
fill(_inStack, false);
_index.resize(graph.size());
fill(_index, UNVISITED_INDEX);
_lowestLink.resize(graph.size());
fill(_lowestLink, 0);
clearStack();
_sccs.clear();
_globalIndex = 1;
}
template <typename Container, typename Value>
void fill(Container c, Value value) {
std::fill(std::begin(c), std::end(c), value);
}
void buildSccs() {
for (int node = 0; node < graph().size(); ++node) {
if (_index[node] == UNVISITED_INDEX) {
dfs(node);
}
}
}
void dfs(int node) {
_index[node] = _globalIndex++;
_lowestLink[node] = _index[node];
pushToStack(node);
for (int neighbour : graph()[node]) {
if (_index[neighbour] == UNVISITED_INDEX) {
dfs(neighbour);
_lowestLink[node] = std::min(_lowestLink[node], _lowestLink[neighbour]);
}
else if (_inStack[neighbour]) {
_lowestLink[node] = std::min(_lowestLink[node], _index[neighbour]);
}
}
if (_index[node] == _lowestLink[node]) {
buildScc(node);
}
}
void buildScc(int node) {
_sccs.emplace_back();
std::vector<int>& scc = _sccs.back();
do {
scc.push_back(popFromStack());
} while (scc.back() != node);
}
void pushToStack(int node) {
_stack.push(node);
_inStack[node] = true;
}
void clearStack() {
while (!_stack.empty()) {
_stack.pop();
}
}
int popFromStack() {
int node = _stack.top();
_stack.pop();
_inStack[node] = false;
return node;
}
const graph_t& graph() {
return *_graph;
}
int _globalIndex;
std::vector< std::vector<int> > _sccs;
std::vector<int> _index;
std::vector<int> _lowestLink;
std::vector<bool> _inStack;
std::stack<int> _stack;
const graph_t* _graph;
};
int main() {
int n, m;
std::cin >> n >> m;
graph_t graph(n);
while (m--) {
int x, y;
std::cin >> x >> y;
x--, y--;
graph[x].push_back(y);
}
std::vector< std::vector<int> > sccs = TarjanSccs().computeSccs(graph);
std::cout << sccs.size() << '\n';
for (const auto& scc : sccs) {
for (int node : scc) {
std::cout << node + 1 << ' ';
}
std::cout << '\n';
}
return 0;
}