Pagini recente » Cod sursa (job #2113126) | Cod sursa (job #2897272) | Cod sursa (job #770303) | Cod sursa (job #3338764) | Cod sursa (job #3336976)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> lista;
vector<bool> viz;
vector<int> tata;
stack<pair<int,int>> stk;
vector<int> nivel;
vector<int> niv_min;
// int cbc;
int n,m;
vector<set<int>> conexe;
void biconexa(int u, int v) {
set<int> tmp;
int x,y;
do {
x = stk.top().first;
y= stk.top().second;
stk.pop();
tmp.insert(x);
tmp.insert(y);
}while (x!=u || y!=v);
conexe.push_back(tmp);
}
void dfs(int i) {
niv_min[i] = nivel[i];
for (int v : lista[i]) {
if (v != tata[i]) {
if (!viz[v]) {
nivel[v] = nivel[i] + 1;
tata[v] = i;
viz[v] = true;
stk.emplace(i,v);
dfs(v);
niv_min[i] = min(niv_min[i], niv_min[v]);
if (nivel[i] <= niv_min[v]) {
// ceva
// cout<<"punct/muchie critica, "<<i<<" "<<v<<endl;
// scoatem de pe stiva tot pana la i,v
biconexa(i,v);
}
}
else {
// muchie intoarcere
niv_min[i] = min(nivel[v], niv_min[i]);
}
}
}
}
int main(){
fin >> n>>m;
lista.resize(n+1);
viz.resize(n+1, false);
tata.resize(n+1);
nivel.resize(n+1);
niv_min.resize(n+1);
for (int i = 0; i<m; i++) {
int u,v;
fin>>u>>v;
lista[u].push_back(v);
lista[v].push_back(u);
}
for (int i = 1; i<=n ; i++) {
if (!viz[i]) {
viz[i] = true;
tata[i] = 0;
nivel[i] = 1;
dfs(i);
}
}
fout<<conexe.size()<<endl;
for (auto cmp : conexe) {
for (auto nod : cmp) {
fout<< nod<<" ";
}
fout<<endl;
}
return 0;
}