Pagini recente » Cod sursa (job #1579533) | Cod sursa (job #1337300) | Cod sursa (job #2351431) | Cod sursa (job #1377240) | Cod sursa (job #1816531)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream f ("biconex.in");
ofstream t ("biconex.out");
vector<int> v[100010];
vector<vector<int> > sol;
vector<pair<int,int> > q;
int niv[100010],nivmin[100010];
bool vaz[100010];
int n,m;
void comp_biconexa(int x,int y)
{
int a,b;
vector<int> aux;
do
{
a=q.back().first,b=q.back().second;
q.pop_back();
aux.push_back(b);
}while(x!=a or y!=b);
aux.push_back(a);
sol.push_back(aux);
}
void dfs(int node,int level){
vaz[node]=true;
niv[node]=nivmin[node]=level;
for (auto i:v[node])
if(!vaz[i]){
q.push_back({node,i});
dfs(i,1+level);
nivmin[node]=min(nivmin[node],nivmin[i]);
if(nivmin[i]>=niv[node]) comp_biconexa(node,i);}
else nivmin[node]=min(nivmin[node],niv[i]);
}
int main()
{
int x,y;
f>>n>>m;
for (int i=0;i<m;++i)
f>>x>>y,v[x].push_back(y),v[y].push_back(x);
for(int i=0;i<n;++i)
if(!vaz[i]) dfs(i,0);
t<<sol.size()<<'\n';
for (auto i:sol){
for (auto j:i)
t<<j<<" ";
t<<'\n';}
return 0;
}