Pagini recente » Cod sursa (job #3336023) | Cod sursa (job #2707192) | Cod sursa (job #3341197) | Cod sursa (job #3356764) | Cod sursa (job #3312754)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int> > graph;
struct componenta_biconexa{
vector<int> tin, low;
vector<vector<int> > componente;
stack<pair<int,int> > s;
componenta_biconexa(vector<vector<int> >& graph, int n)
:tin(n+1, -1), low(n+1)
{
dfs(graph, 1, 0, 0);
}
void punct_de_articulatie(int x, int y){
int tx, ty;
vector<int> v;
while(tx!=x or ty!=y){
tx=s.top().first;
ty=s.top().second;
s.pop();
v.push_back(tx);
v.push_back(ty);
}
componente.push_back(v);
}
void dfs(vector<vector<int> >& graph, int nod, int parent, int k){
tin[nod]=low[nod]=k;
for(auto it:graph[nod]){
if(it!=parent and tin[it]==-1){
s.push({nod,it});
dfs(graph, it, nod, k+1);
low[nod]=min(low[nod], low[it]);
if(low[it]>=tin[nod]){
punct_de_articulatie(nod, it);
}
}else if(tin[it]!=-1){
low[nod]=min(low[nod], tin[it]);
}
}
}
void query(){
cout<<component.size()<<'\n';
for(auto it:componente){
sort(it.begin(),it.end());
it.erase(unique(it.begin(),it.end()), it.end());
for(auto i:it){
fout<<i<<' ';
}
fout<<'\n';
}
}
};
int main(){
int n, m;
fin>>n>>m;
graph.resize(n+1);
for(int i=1;i<=m;i++){
int x, y;
fin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
componenta_biconexa ans(graph, n);
ans.query();
}