Pagini recente » Cod sursa (job #1498162) | Cod sursa (job #1478403) | Cod sursa (job #2630589) | Cod sursa (job #363486) | Cod sursa (job #3269035)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int nodes, edges, num, numCtc;
vector <int> graph[100001], ctc[100001];
vector <int> stack;
bool inStack[100001];
int id[100001], low[100001];
void dfs (int x){
id[x] = ++num;
low[x] = id[x];
inStack[x] = true;
stack.push_back(x);
for (auto idx:graph[x]){
if (id[idx] == 0){ // nu am mai fost pe acolo
dfs(idx);
low[x] = min(low[x], low[idx]);
}
else if (inStack[idx] == true){ // ii un back edge care perge in sus
low[x] = min(low[x], id[idx]);
}
}
if (low[x] == id[x]){
while (stack.back() != x){
ctc[numCtc].push_back(stack.back());
inStack[stack.back()] = false;
stack.pop_back();
}
ctc[numCtc].push_back(stack.back());
inStack[stack.back()] = false;
stack.pop_back();
numCtc++;
}
}
int main (){
int x, y;
in >> nodes >> edges;
for (int i=1; i<=edges; ++i){
in >> x >> y;
graph[x].push_back(y);
}
for (int i=1; i<=nodes; ++i){
if (id[i] == 0){
dfs(i);
}
}
out << numCtc << '\n';
for (int i=0; i<numCtc; ++i){
for (auto idx:ctc[i])
out << idx << ' ';
out << '\n';
}
return 0;
}