Pagini recente » Cod sursa (job #1624969) | Cod sursa (job #591831) | Cod sursa (job #2445990) | Cod sursa (job #475068) | Cod sursa (job #1166095)
#include <fstream>
#include <vector>
#include <algorithm>
#define maxn 100001
#define vint vector<int>::iterator
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int viz[maxn],st[maxn],lowlink[maxn],depth[maxn],t,n,m,a,b,nrb;
vector<int> G[maxn],CB[maxn];
void dfs (int x, int lvl)
{
viz[x] = 1;
lowlink[x] = lvl;
depth[x] = lvl;
st[++t] = x;
for (vint it = G[x].begin(); it != G[x].end(); ++it)
{
if (!viz[*it])
{
dfs (*it,lvl+1);
lowlink[x] = min (lowlink[x],lowlink[*it]);
if (lowlink[*it] >= lvl)
{
++nrb;
while (st[t] != x)
{
CB[nrb].push_back (st[t]);
--t;
}
CB[nrb].push_back (x);
}
}
else
{
lowlink[x] = min (lowlink[x],depth[*it]);
}
}
}
int main()
{
fin>>n>>m;
for (int i=1; i<=m; ++i)
{
fin>>a>>b;
G[a].push_back (b);
G[b].push_back (a);
}
for (int i=1; i <=n; ++i)
{
if (!viz[i])
dfs (i,1);
}
fout<<nrb<<"\n";
for (int i=1; i<=nrb; ++i)
{
for (vint it = CB[i].begin(); it != CB[i].end(); ++it)
fout<<*it<<" ";
fout<<"\n";
}
}