Pagini recente » Cod sursa (job #2008227) | Cod sursa (job #805523) | Cod sursa (job #404631) | Cod sursa (job #1045253) | Cod sursa (job #1376155)
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
typedef vector<int> VI;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define foor(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
#define inf 0x3f3f3f3f
int n,m,x,y,i;
vector<VI> G,comp;
VI stiva,low,lev;
vector<bool> viz;
void dfs(int nod,int level)
{
viz[nod]=true;
stiva.push_back(nod);
lev[nod]=low[nod]=level;
foor(it,G[nod]) if(!viz[*it])
{
dfs(*it,level+1);
if(low[*it]>=lev[nod])
{
comp.resize(comp.size()+1);
while(stiva.back()!=nod)
{
comp.back().push_back(stiva.back());
stiva.pop_back();
}
comp.back().push_back(nod);
}
low[nod]=min(low[nod],low[*it]);
}
else low[nod]=min(low[nod],lev[*it]);
}
int main()
{
f>>n>>m;
G.resize(n+1);
low.resize(n+1,inf);
viz.resize(n+1);
lev.resize(n+1);
for(;m;--m)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(i=1;i<=n;++i) if(!viz[i]) dfs(i,1),stiva.pop_back();
g<<comp.size()<<'\n';
foor(itc,comp)
{
foor(it,(*itc)) g<<*it<<' ';
g<<'\n';
}
return 0;
}