Pagini recente » Cod sursa (job #645792) | Cod sursa (job #409556) | Cod sursa (job #2866024) | Cod sursa (job #537355) | Cod sursa (job #3292361)
#include <bits/stdc++.h>
#define inf 100000000000000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int level[100005];
int low[100005], root;
int tata[100005], n;
vector<int> L[100005];
///vector<pair<int, int>> edges;
vector< set<int> > Componente;
bitset<100005> viz;
///bitset<100005> NodCritic;
stack< pair<int, int> > st;
void Citire() {
int m, x, y;
fin >> n >> m;
for(int i = 1; i <= m; i++) {
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
}
void ComponenteBiconexe(int x, int y) {
int tx, ty;
set<int> aux;
do {
tx = st.top().first;
ty = st.top().second;
st.pop();
aux.insert(tx);
aux.insert(ty);
} while(x != tx && y != ty);
Componente.push_back(aux);
}
void Dfs(int nod) {
level[nod] = level[tata[nod]] + 1;
low[nod] = level[nod];
viz[nod] = 1;
for(int i : L[nod])
if(i != tata[nod]) {
if(viz[i] == 1)
low[nod] = min(level[i], low[nod]);
else {
tata[i] = nod;
st.push({nod, i});
Dfs(i);
low[nod] = min(low[nod], low[i]);
if(level[nod] <= low[i])
ComponenteBiconexe(nod, i);
}
}
}
void Afis() {
fout << Componente.size() << "\n";
for(auto e : Componente) {
for(int i : e)
fout << i << " ";
fout << "\n";
}
}
void Solution() {
for(int i = 1; i <= n; i++)
if(!viz[i]) Dfs(i);
Afis();
}
int main() {
ios_base :: sync_with_stdio(0);
fin.tie(0);
fout.tie(0);
Citire();
Solution();
fin.close();
fout.close();
return 0;
}