Pagini recente » Cod sursa (job #269192) | Cod sursa (job #1744099) | Cod sursa (job #3247748) | Cod sursa (job #788358) | Cod sursa (job #2928328)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
using AdjList = vector<vector<int>>;
class Tarjan {
const int UNVISITED = -1;
const AdjList &adjList;
int nodeCount;
int currentId = 0;
vector<int> ids;
vector<int> lowlink;
vector<bool> isOnStack;
stack<int> nodeStack;
vector<vector<int>> components;
void dfs(int node) {
ids[node] = lowlink[node] = currentId++;
isOnStack[node] = true;
nodeStack.push(node);
for (int nextNode : adjList[node]) {
if (ids[nextNode] == UNVISITED) {
dfs(nextNode);
}
if (isOnStack[nextNode]) {
lowlink[node] = min(lowlink[node], lowlink[nextNode]);
}
}
if (ids[node] == lowlink[node]) {
components.emplace_back();
// Pop stack until after the current node
while (true) {
auto topNode = nodeStack.top();
nodeStack.pop();
isOnStack[topNode] = false;
// Set component id
lowlink[topNode] = ids[node];
components.back().push_back(topNode);
if (topNode == node) break;
}
}
}
public:
Tarjan(AdjList &adjList)
: adjList(adjList)
, nodeCount(adjList.size())
, ids(nodeCount, UNVISITED)
, lowlink(nodeCount)
, isOnStack(nodeCount, false) {}
vector<vector<int>> run() {
for (int node = 1; node < nodeCount; ++node) {
if (ids[node] == UNVISITED) {
dfs(node);
}
}
return components;
}
};
int main() {
ifstream fin("ctc.in");
int nodeCount, edgeCount;
fin >> nodeCount >> edgeCount;
AdjList adjList(nodeCount + 1);
// Read edges
for (int i = 0; i < edgeCount; ++i) {
int node1, node2;
fin >> node1 >> node2;
adjList[node1].push_back(node2);
}
Tarjan tarjan(adjList);
auto components = tarjan.run();
ofstream fout("ctc.out");
fout << components.size() << '\n';
for (const auto &component : components) {
for (int node : component) {
fout << node << ' ';
}
fout << '\n';
}
return 0;
}