Pagini recente » Cod sursa (job #2586175) | Cod sursa (job #1490264) | Cod sursa (job #2945798) | Cod sursa (job #2888906) | Cod sursa (job #2197953)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<int> adj[kNmax];
//vector<int> color;
//vector<int> critic;
vector<int> parent;
vector<int> idx;
vector<int> lowLink;
int timp;
stack<int> stiva;
void read_input() {
ifstream fin("biconex.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void DFS(vector<vector<int>> &componente, int nod) {
//color[nod] = 1;
idx[nod] = lowLink[nod] = ++timp;
vector<int>::iterator it;
stiva.push(nod);
//int childCounter = 0;
for (it = adj[nod].begin(); it != adj[nod].end(); ++it) {
if (*it != parent[nod]) {
//if (!color[*it]) {
if (!idx[*it]) {
//childCounter++;
parent[*it] = nod;
DFS(componente, *it);
if (lowLink[nod] > lowLink[*it]) {
lowLink[nod] = lowLink[*it];
}
if (idx[nod] < lowLink[*it]) {
vector<int> v;
v.push_back(nod);
v.push_back(*it);
componente.push_back(v);
// muchie critica - deci capetele formeaza o componenta biconexa
}
}
else { // intotdeauna gri ptr grafuri neorientate
if (lowLink[nod] > idx[*it])
lowLink[nod] = idx[*it];
}
}
}
if (idx[nod] == lowLink[nod]) {
if (stiva.top() != nod) {
vector<int> v;
int x;
do {
x = stiva.top();
v.push_back(x);
//color[x] = 2;
stiva.pop();
} while (x != nod);
componente.push_back(v);
} // un element nu formeaza o componenta
}
}
vector<vector<int>> get_result() {
for (int i = 0; i <= n; ++i) {
//color.push_back(0);
//critic.push_back(0);
parent.push_back(0);
idx.push_back(0);
lowLink.push_back(0);
}
vector<vector<int>> componente;
for (int i = 1; i <= n; ++i) {
//if (!color[i]) {
timp = 0;
if (!idx[i]) {
DFS(componente, i);
}
}
/*
TODO: Gasiti muchiile critice ale grafului neorientat stocat cu liste
de adiacenta in adj.
*/
return componente;
}
void print_output(vector<vector<int>> result) {
ofstream fout("biconex.out");
fout << result.size() << '\n';
for (const auto& ctc : result) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}