Pagini recente » Cod sursa (job #2329207) | Cod sursa (job #2516191) | Cod sursa (job #1421971) | Cod sursa (job #2552086) | Cod sursa (job #3229000)
#include <bits/stdc++.h>
using namespace std;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
struct Edge {
int x;
int y;
Edge() { }
Edge(int x, int y)
: x(x)
, y(y) { }
bool operator==(const Edge& other) { return x == other.x && y == other.y; }
bool operator!=(const Edge& other) { return !(*this == other); }
};
// numarul maxim de noduri
static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
vector<int> adj[NMAX];
void read_input() {
ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y; // muchia (x, y)
adj[x].push_back(y);
adj[y].push_back(x);
}
fin.close();
}
void tarjan_bcc_dfs(int node, vector<int>& parent, int& timestamp, vector<int>& found, vector<int>& low_link,
stack<Edge>& st, vector<vector<int>>& all_bccs) {
// new node visited
found[node] = timestamp++;
low_link[node] = found[node];
st.push(Edge(parent[node], node));
// visit neighbours
int children = 0;
for (auto neigh : adj[node]) {
if (parent[neigh] != -1) { // already visited
if (neigh != parent[node]) { // trb sa ignoram muchia de intoarcere spre parinte
low_link[node] = min(low_link[node], found[neigh]);
}
continue;
}
// not visited
parent[neigh] = node;
children++;
tarjan_bcc_dfs(neigh, parent, timestamp, found, low_link, st, all_bccs);
low_link[node] = min(low_link[node], low_link[neigh]);
// check if we found a bcc
if (low_link[neigh] >= found[node]) {
vector<int> bcc;
bcc.push_back(node);
while (st.top() != Edge(node, neigh)) {
bcc.push_back(st.top().y);
st.pop();
}
bcc.push_back(st.top().y);
st.pop();
all_bccs.push_back(bcc);
}
}
}
void tarjan_bcc(vector<vector<int>>& all_bccs) {
vector<int> parent(n + 1, -1);
vector<int> found(n + 1, INT_MAX);
vector<int> low_link(n + 1, INT_MAX);
stack<Edge> st;
int timestamp = 0;
for (int i = 1; i <= n; i++) {
if (parent[i] == -1) {
parent[i] = i; // convention for root
tarjan_bcc_dfs(i, parent, timestamp, found, low_link, st, all_bccs);
}
}
}
vector<vector<int>> get_result() {
//
// TODO: Găsiți componentele biconexe (BCC) ale grafului neorientat cu n noduri, stocat în adj.
//
// Rezultatul se va returna sub forma unui vector, fiecare element fiind un BCC (adică tot un vector).
// * nodurile dintr-un BCC pot fi găsite în orice ordine
// * BCC-urile din graf pot fi găsite în orice ordine
//
// Indicație: Folosiți algoritmul lui Tarjan pentru BCC.
//
vector<vector<int>> all_bccs;
tarjan_bcc(all_bccs);
return all_bccs;
}
void print_output(const vector<vector<int>>& all_bccs) {
ofstream fout("biconex.out");
fout << all_bccs.size() << '\n';
for (auto& bcc : all_bccs) {
for (auto node : bcc) {
fout << node << " ";
}
fout << "\n";
}
fout.close();
}
};
// [ATENTIE] NU modifica functia main!
int main() {
// * se aloca un obiect Task pe heap
// (se presupune ca e prea mare pentru a fi alocat pe stiva)
// * se apeleaza metoda solve()
// (citire, rezolvare, printare)
// * se distruge obiectul si se elibereaza memoria
auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
if (!task) {
cerr << "new failed: WTF are you doing? Throw your PC!\n";
return -1;
}
task->solve();
delete task;
return 0;
}