Pagini recente » Cod sursa (job #1876913) | Cod sursa (job #2259402) | Cod sursa (job #395334) | Cod sursa (job #1758627) | Cod sursa (job #2928663)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Tarjan {
private:
int N, M, id, ctc_count;
vector<vector<int>> adj_list;
vector<int> ids;
vector<int> low;
vector<bool> sel;
stack<int> st;
vector<int> ctc;
unordered_map<int, vector<int>> componente;
public:
Tarjan(int N, int M, vector<vector<int>> adj_list) {
this->N = N;
this->M = M;
this->adj_list = std::move(adj_list);
this->ids.resize(N+1, -1);
this->low.resize(N+1, 0);
this->sel.resize(N+1, false);
this->ctc.resize(N+1);
this->id = 0;
this->ctc_count = 0;
componente.reserve(N+1);
}
void dfs(int node) {
st.push(node);
sel[node] = true;
ids[node] = id;
low[node] = id++;
for (auto neighbour : adj_list[node]) {
if (ids[neighbour] == -1)
dfs(neighbour);
if (sel[neighbour])
low[node] = min(low[node], low[neighbour]);
}
if (ids[node] == low[node]) {
while(!st.empty()) {
int el = st.top();
sel[el] = false;
ctc[el] = ctc_count;
componente[ctc_count].push_back(el);
st.pop();
if (el == node)
break;
}
ctc_count++;
}
}
unordered_map<int, vector<int>> findCtc() {
for (int i = 1; i <= N; i++) {
if (ids[i] == -1) {
dfs(i);
}
}
return componente;
}
int get_ctc_count() const {
return this->ctc_count;
}
};
int main() {
ifstream fin("ctc.in");
fstream fout("ctc.out");
int n, m, a, b;
fin >> n >> m;
vector<vector<int>> lista_ad(n + 1);
for (int i = 1; i <= m; i++) {
fin >> a >> b;
lista_ad[a].push_back(b);
}
Tarjan tarjan(n, m, lista_ad);
unordered_map<int, vector<int>> ctc = tarjan.findCtc();
int count = tarjan.get_ctc_count();
fout << count << '\n';
for (const auto& componenta : ctc) {
vector<int> aux = componenta.second;
std::sort(aux.begin(), aux.end());
for (auto nod : aux)
fout << nod << ' ';
fout << endl;
}
return 0;
}