Pagini recente » Cod sursa (job #2652560) | Cod sursa (job #1129173) | Cod sursa (job #1966695) | Cod sursa (job #2696696) | Cod sursa (job #522577)
Cod sursa(job #522577)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n,m;
vector<int> V[1<<17];
vector<vector<int> > C;
stack<int> ST;
int minh[1<<17];
int H[1<<17];
void pop_comp(int x, int tat)
{
vector<int> comp;
while (ST.size() > 0 && ST.top() != x)
{
comp.push_back(ST.top());
ST.pop();
}
if (ST.size() > 0)
{
comp.push_back(ST.top());
ST.pop();
}
if (tat != -1) comp.push_back(tat);
C.push_back(comp);
}
void df(int x,int tat)
{
ST.push(x);
for (size_t i=0;i<V[x].size();i++)
if (!H[V[x][i]])
{
H[V[x][i]] = H[x] + 1;
df(V[x][i],x);
if (minh[V[x][i]] < minh[x]) minh[x] = minh[V[x][i]];
}
else
{
if (H[V[x][i]] < minh[x]) minh[x] = H[V[x][i]];
}
if (tat != -1 && minh[x] == H[tat])
pop_comp(x,tat);
}
int main()
{
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
scanf ("%d%d",&n,&m);
memset(minh,1,sizeof(minh));
for (;m;m--)
{
int a,b;
scanf ("%d%d",&a,&b);
V[a].push_back(b);
V[b].push_back(a);
}
for (int i=1;i<=n;i++)
if (!H[i])
{
H[i] = 1;
df(i,-1);
}
printf ("%d\n",C.size());
for (size_t i=0;i<C.size();i++)
{
for (size_t j=0;j<C[i].size();j++)
printf ("%d ",C[i][j]);
printf ("\n");
}
return 0;
}