Pagini recente » Cod sursa (job #2280710) | Cod sursa (job #2724473) | Cod sursa (job #917194) | Cod sursa (job #2341534) | Cod sursa (job #2197962)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
struct Edge {
int x;
int y;
};
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<Edge> stiva;
set<int> _set;
vector<set<int>> componente;
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(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;
stiva.push({ nod, *it });
DFS(*it);
if (lowLink[nod] > lowLink[*it]) {
lowLink[nod] = lowLink[*it];
}
if (idx[nod] <= lowLink[*it]) {
int x, y;
componente.push_back(_set);
set<int> &v = componente[componente.size()-1];
do {
x = stiva.top().x;
y = stiva.top().y;
stiva.pop();
v.insert(x);
v.insert(y) ;
} while (x != nod && y != nod);
// 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
}*/
}
void 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);
}
for (int i = 1; i <= n; ++i) {
//if (!color[i]) {
timp = 0;
if (!idx[i]) {
DFS(i);
}
}
/*
TODO: Gasiti muchiile critice ale grafului neorientat stocat cu liste
de adiacenta in adj.
*/
}
void print_output() {
ofstream fout("biconex.out");
fout << componente.size() << '\n';
for (const auto& ctc : componente) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}