Pagini recente » Cod sursa (job #602812) | Cod sursa (job #182818) | Cod sursa (job #3351595) | Cod sursa (job #1964768) | Cod sursa (job #1378052)
#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,int fat)
{
viz[nod]=true;
stiva.push_back(nod);
lev[nod]=low[nod]=level;
foor(it,G[nod])
{
if(!viz[*it])
{
dfs(*it,level+1,nod);
if(low[*it]>=lev[nod])
{
comp.resize(comp.size()+1);
while(stiva.back()!=*it)
{
comp.back().push_back(stiva.back());
stiva.pop_back();
}
comp.back().push_back(nod);
comp.back().push_back(*it);
stiva.pop_back();
}
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,0);
stiva.pop_back();
if(G[i].size()==0)
{
comp.resize(comp.size()+1);
comp.back().push_back(i);
}
}
g<<comp.size()<<'\n';
foor(itc,comp)
{
foor(it,(*itc)) g<<*it<<' ';
g<<'\n';
}
return 0;
}