Pagini recente » Cod sursa (job #822959) | Cod sursa (job #1742646) | Cod sursa (job #618247) | Cod sursa (job #578030) | Cod sursa (job #2575518)
#include <bits/stdc++.h>
#define nMax 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, x, y, t, k, biconex, low[nMax], ind[nMax], S[nMax];
vector<int> G[nMax], cx[nMax];
void dfs(int nod)
{
low[nod]=t;
ind[nod]=t;
t++;
S[++k]=nod;
for(auto i:G[nod])
if(ind[i]==0)
{
dfs(i);
if(low[i]>=ind[nod])
{
biconex++;
while(S[k]!=i)
{
cx[biconex].push_back(S[k]);
k--;
}
cx[biconex].push_back(S[k]);
k--;
cx[biconex].push_back(nod);
}
low[nod]=min(low[i], low[nod]);
}
else
low[nod]=min(low[nod], ind[i]);
}
int main()
{
fin >> n >> m;
while(m--)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(ind[i]==0)
{
t=0;
k=0;
dfs(i);
}
fout << biconex << "\n";
for(int i=1; i<=biconex; i++)
{
for(auto j:cx[i])
fout << j << " ";
fout << "\n";
}
return 0;
}