Pagini recente » Cod sursa (job #539715) | Cod sursa (job #1714430) | Cod sursa (job #2930542) | Cod sursa (job #699837) | Cod sursa (job #3228875)
#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];
vector<int>parent;
vector<int>low_link;
vector<int>found;
stack<Edge> edges_stack;
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();
}
vector<vector<int>> tarjan(){
vector<vector<int>> all_bcc;
parent=vector<int>(n+1,-1);
low_link=vector<int>(n+1,-1);
found=vector<int>(n+1,-1);
int timestamp=0;
for(int i=1;i<=n;++i)
if(parent[i]==-1) {
parent[i]=i;
dfs(i,timestamp,all_bcc);
}
return all_bcc;
}
void dfs(int node,int ×tamp,vector<vector<int>> &all_bcc){
found[node]=++timestamp;
low_link[node]=found[node];
for(auto &neight:adj[node]){
if(parent[neight]!=-1){
if(neight!=parent[node]){
low_link[node]=min(low_link[node],found[neight]);
}
continue;
}
parent[neight]=node;
edges_stack.push(Edge(node,neight));
dfs(neight,timestamp,all_bcc);
low_link[node]=min(low_link[node],low_link[neight]);
if(low_link[neight]>=found[node]){
all_bcc.push_back(transform_stack_to_bcc(Edge(node,neight)));
}
}
}
vector<int> transform_stack_to_bcc(Edge final){
unordered_set<int> bcc;
Edge edge;
Edge e;
do {
e = edges_stack.top();
edges_stack.pop();
bcc.insert(e.x);
bcc.insert(e.y);
} while (e != final);
return vector<int>{bcc.begin(), bcc.end()};
}
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.
//
return tarjan();
}
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;
}