Pagini recente » Cod sursa (job #1491637) | Cod sursa (job #2400241) | Cod sursa (job #1510088) | Cod sursa (job #2821500) | Cod sursa (job #3275535)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, lastIndex, ctc;
vector<vector<int>> graph, ans;
vector <int> index, lowlink, current;
vector <bool> visited, inStack;
stack <int> stk;
void init() {
graph = vector<vector<int>> (n + 1);
index = vector <int> (n + 1);
lowlink = vector <int> (n + 1);
visited = vector <bool> (n + 1);
inStack = vector <bool> (n + 1);
}
void read() {
fin >> n >> m;
init();
int x, y;
for(int i = 1; i <= m; i ++) {
fin >> x >> y;
graph[x].push_back(y);
}
}
void tarjan(int node) {
visited[node] = true;
inStack[node] = true;
stk.push(node);
index[node] = lowlink[node] = ++lastIndex;
for(const auto& neighbour : graph[node]) {
if(!visited[neighbour]) {
tarjan(neighbour);
lowlink[node] = min(lowlink[node], lowlink[neighbour]);
} else if(inStack[neighbour]) {
lowlink[node] = min(lowlink[node], index[neighbour]);
}
}
if(lowlink[node] == index[node]) {
++ctc;
int stackNode;
current.clear();
do {
stackNode = stk.top();
inStack[stackNode] = false;
stk.pop();
current.push_back(stackNode);
} while(stackNode != node);
ans.push_back(current);
}
}
void solve() {
for(int i = 1; i <= n; i ++)
if(!visited[i])
tarjan(i);
}
void print() {
fout << ctc << '\n';
for(int i = 0; i < ctc; i ++, fout << '\n')
for(const auto& node : ans[i])
fout << node << " ";
}
int main() {
read();
solve();
print();
}