Pagini recente » Cod sursa (job #1869321) | Cod sursa (job #1148895) | Cod sursa (job #2396721) | Cod sursa (job #1034793) | Cod sursa (job #1451479)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100100
#define INF 999999999
#define UNDEFINED 0
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> graph[NMAX];
vector<vector<int> > solution;
stack<int> s;
int idx[NMAX]; // timpul de descoperire
int lowlink[NMAX]; // timpul de descoperire al celui mai indepartat stramos (back edges)
bool isInStack[NMAX];
int nodes, index;
inline void printSolution() {
out << solution.size() << "\n";
for (unsigned i = 0; i < solution.size(); i++) {
for (unsigned j = 0; j < solution.at(i).size(); j++) {
out << solution.at(i).at(j) + 1 << " ";
}
out << "\n";
}
}
void dfsTarjan(int start) {
index++;
idx[start] = index;
lowlink[start] = index;
isInStack[start] = true;
s.push(start);
for (unsigned int i = 0; i < graph[start].size(); i++) {
int neighbour = graph[start].at(i);
if (idx[neighbour] == UNDEFINED) {
dfsTarjan(neighbour);
lowlink[start] = min(lowlink[start], lowlink[neighbour]);
}
else if (isInStack[neighbour]) {
lowlink[start] = min(lowlink[start], idx[neighbour]);
}
}
if (lowlink[start] == idx[start]) {
vector<int> sol;
while (s.top() != start) {
sol.push_back(s.top());
isInStack[s.top()] = false;
s.pop();
}
sol.push_back(s.top());
isInStack[s.top()] = false;
s.pop();
solution.push_back(sol);
}
}
void Tarjan() {
index = 0;
for (int i = 0; i < nodes; i++) {
if (idx[i] == UNDEFINED) {
dfsTarjan(i);
}
}
printSolution();
}
int main() {
int edges, x, y;
in >> nodes >> edges;
for (int i = 0; i < edges; i++) {
in >> x >> y;
graph[x - 1].push_back(y - 1);
}
Tarjan();
return 0;
}