Pagini recente » Cod sursa (job #2715163) | Cod sursa (job #399786) | Cod sursa (job #1408099) | Cod sursa (job #2150878) | Cod sursa (job #2925281)
#include <bits/stdc++.h>
#include <utility>
using namespace std;
class Graph {
private:
vector<vector<int>> gr;
int n;
vector<int> viz; ///vector de vizitati pentru graf
public:
Graph(vector<vector<int>> gr_, int n_) : gr(std::move(gr_)), n(n_) {
viz.resize(n + 1, 0); ///initializarea vectorului
}
///implementarea algoritmului lui Tarjan
///folosind recursivitate de tip DFS
void Tarjan(int node, int& level, vector<int>& initialLevel, vector<int>& minLevel,
stack<int>& st, vector<bool>& isInStack,
vector<vector<int>>& ctc) {
if(minLevel[node] >= 0){
return;
}
level += 1; ///trecerea la urmatorul nivel al grafului
initialLevel[node] = level;
minLevel[node] = level;
st.push(node); ///punerea in stiva
isInStack[node] = true;
for(int child: gr[node]){
Tarjan(child, level, initialLevel, minLevel, st, isInStack, ctc);
///parcurgerea grafului orientat cu DFS pt Tarjan
if(isInStack[child]){
minLevel[node] = min(minLevel[node], minLevel[child]);
}
}
if(initialLevel[node] == minLevel[node]){
ctc.push_back({}); ///am gasit un nou CTC
int x = -1;
do{
x = st.top();
st.pop();
isInStack[x] = false;
ctc.back().push_back(x);
}while(x != node);
}
}
};
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
///implementarea citirii
f >> n >> m;
vector<vector<int>> gr(n + 1);
for(int x, y, i = 1; i <= m; i++) {
f >> x >> y;
gr[x].push_back(y);
}
///crearea obiectului de tip Graph
Graph grf(gr, n);
int level = 0;
vector<int> initialLevel(n + 1, -1);
vector<int> minLevel(n + 1, -1);
stack<int> st;
vector<bool> isInStack(n + 1, false);
vector<vector<int>> ctc;
///declarea structurilor de date necesare
///pt rezolvarea problemei cu Tarjan
for(int node = 1; node <= n; ++node){
if(minLevel[node] < 0){
grf.Tarjan(node, level, initialLevel, minLevel, st, isInStack, ctc);
}
}
///afisarea
g << ctc.size() << "\n";
for(vector<int>& nodes: ctc){
for(int node: nodes){
g << node << " ";
}
g << "\n";
}
g.close();
return 0;
}