Pagini recente » Cod sursa (job #2610735) | Cod sursa (job #1798070) | Cod sursa (job #1886141) | Borderou de evaluare (job #2768045) | Cod sursa (job #2928557)
// CTC - TARJAN
// Created by Radu Buzas on 22.10.2022.
//
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define min(a, b) ( (a < b) ? a : b)
ifstream in("ctc.in");
ofstream out("ctc.out");
int incide = 1;
void dfs(vector<vector<int>> & graph, vector<int> & id, vector<int> & low, stack<int> & s, vector<bool> &inStack, vector<vector<int>> & sol, int k){
inStack[k] = true;
low[k] = id[k] = incide++;
s.push(k);
for (auto x : graph[k]) {
if(!id[x])
dfs(graph, id, low, s, inStack, sol, x), low[k] = min(low[k], low[x]);
else if(inStack[x])
low[k] = min(low[k], low[x]);
}
if(id[k] == low[k]){
vector<int> tmp;
while(s.top() != k)
inStack[s.top()] = 0, tmp.push_back(s.top()) , s.pop();
inStack[s.top()] = 0, tmp.push_back(s.top()), s.pop();
sol.push_back(tmp);
tmp.clear();
}
}
int main(){
int n, m, x, y;
in >> n >> m;
vector<vector<int>> graph(n +1), sol;
vector<int> id(n+1, 0), low(n+1, 0);
vector<bool> boolV(n+1, 0);
stack<int> s;
while(m--){
in >> x >> y;
graph[x].push_back(y);
}
in.close();
for(int i = 1; i <= n; i++)
if(!id[i])
dfs(graph, id, low,s, boolV, sol, i);
out << sol.size() << '\n';
for (auto x : sol) {
sort(x.begin(), x.end());
for (auto y: x) {
out << y << ' ';
}
out << '\n';
}
return 0;
}