Pagini recente » Cod sursa (job #1218088) | Cod sursa (job #563279) | Cod sursa (job #3141152) | Cod sursa (job #191120) | Cod sursa (job #3192683)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
typedef long long ll;
typedef long double ld;
vector <int> v[100005];
int tin[100005],low[100005];
int viz[100005];
int n,m;
int root;
vector <int> stiva;
vector <int> comp;
vector<vector <int>> biconexe;
void dfs(int nod,int par)
{
stiva.push_back(nod);
viz[nod]=1;
tin[nod]=tin[par]+1;
low[nod]=tin[nod];
for(auto x:v[nod])
if(x!=par)
{
if(viz[x]==1)
{
low[nod]=min(low[nod],tin[x]);
}
else
{
dfs(x,nod);
low[nod]=min(low[nod],low[x]);
if(tin[nod]<=low[x])
{
comp.clear();
while(stiva[stiva.size()-1]!=x)
{
comp.push_back(stiva[stiva.size()-1]);
stiva.pop_back();
}
comp.push_back(x);
stiva.pop_back();
comp.push_back(nod);
biconexe.push_back(comp);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
dfs(i,0);
fout<<biconexe.size()<<'\n';
for(int i=0;i<biconexe.size();i++)
{
for(int j=0;j<biconexe[i].size();j++)
fout<<biconexe[i][j]<<' ';
fout<<'\n';
}
return 0;
}