Pagini recente » Autentificare | Borderou de evaluare (job #1921715) | Cod sursa (job #2306062)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define INPUT_FILE_PATH "ctc.in"
#define OUTPUT_FILE_PATH "ctc.out"
#define UNDEFINED -1
using namespace std;
class Graph {
public:
Graph(int n) : n(n) {
index = new int[n];
lowLink = new int[n];
isInStack = new bool[n];
fill(index, index + n, UNDEFINED);
fill(lowLink, lowLink + n, UNDEFINED);
fill(isInStack, isInStack + n, false);
for (int i = 0; i < n; ++i) {
adjMatrix.emplace_back(vector<int>());
}
}
void addEdge(int from, int to) {
adjMatrix[from].emplace_back(to);
}
vector<vector<int>> getStrongConnectedComponents() {
currIndex = 0;
for (int i = 0; i < n; ++i) {
if (index[i] == UNDEFINED) {
tarjan(i);
}
}
return strongConnectedComponents;
}
private:
int n;
int *index;
int *lowLink;
bool *isInStack;
int currIndex;
vector<vector<int>> adjMatrix;
vector<vector<int>> strongConnectedComponents;
stack<int> st;
void tarjan(int node) {
index[node] = currIndex++;
lowLink[node] = index[node];
st.push(node);
isInStack[node] = true;
for (int target : adjMatrix[node]) {
if (index[target] == UNDEFINED) {
tarjan(target);
lowLink[node] = min(lowLink[node], lowLink[target]);
} else if (isInStack[target]) {
lowLink[node] = min(lowLink[node], lowLink[target]);
}
}
if (index[node] == lowLink[node]) {
strongConnectedComponents.emplace_back(vector<int>());
int top;
do {
top = st.top();
isInStack[node] = false;
st.pop();
strongConnectedComponents[strongConnectedComponents.size() - 1].push_back(top);
} while (top != node);
}
}
};
int main() {
ifstream cin(INPUT_FILE_PATH);
ofstream cout(OUTPUT_FILE_PATH);
int n, m;
cin >> n >> m;
Graph graph(n);
while (m--) {
int from, to;
cin >> from >> to;
--from;
--to;
graph.addEdge(from, to);
}
vector<vector<int>> strongConnComponents = graph.getStrongConnectedComponents();
cout << strongConnComponents.size() << "\n";
for (const vector<int> &nodes : strongConnComponents) {
for (int node : nodes) {
cout << node + 1 << " ";
}
cout << "\n";
}
return 0;
}