Pagini recente » Cod sursa (job #1727751) | Cod sursa (job #432368) | Cod sursa (job #2073807) | Cod sursa (job #2809750) | Cod sursa (job #3196679)
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,id[NMAX],low[NMAX],bcc,i,j,x,y,timp,onstack[NMAX];
vector<int>v[NMAX],bc[NMAX];
stack<int>s;
void dfs(int node)
{
id[node]=low[node]=++timp;
s.push(node);
onstack[node]=1;
for(auto it:v[node])
{
if(id[it])
{
low[node]=min(low[node],id[it]);
continue;
}
dfs(it);
low[node]=min(low[node],low[it]);
if(id[node]<=low[it])
{
bcc++;
while(s.top()!=it)
{
bc[bcc].push_back(s.top());
s.pop();
}
bc[bcc].push_back(it);
s.pop();
bc[bcc].push_back(node);
}
}
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=n;i++)
if(id[i]==0)
dfs(i);
fout<<bcc<<'\n';
for(i=1;i<=bcc;i++)
{
for(auto it:bc[i])
fout<<it<<" ";
fout<<'\n';
}
return 0;
}