Pagini recente » Cod sursa (job #1451536) | Cod sursa (job #1047615) | Cod sursa (job #901347) | Cod sursa (job #2586432) | Cod sursa (job #426227)
Cod sursa(job #426227)
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 200002
#define f first
#define s second
int n, m, nr, comp, viz[nmax], min_level[nmax], level[nmax], last[nmax];
vector<int> v[nmax];
vector<int> sol[nmax];
pair<int, int> st[nmax];
void print(int x)
{
if(last[x]!=comp)
{
sol[comp].push_back(x);
last[x]=comp;
}
}
void dfs(int nod)
{
viz[nod] = 1;
min_level[nod] = level[nod];
for(vector<int>::iterator it = v[nod].begin(); it!=v[nod].end(); it++)
if(!viz[*it])
{
level[*it] = level[nod] + 1;
st[++nr] = make_pair(min(nod, *it), max(nod, *it));
dfs(*it);
min_level[nod] = min(min_level[nod], min_level[*it]);
if(min_level[*it] >= level[nod])
{
comp++;
while(st[nr] != make_pair(min(nod, *it), max(nod, *it)))
{
print(st[nr].f);
print(st[nr].s);
nr--;
}
print(st[nr].f);
print(st[nr].s);
nr--;
}
}
else
{
if (level[*it] < level[nod] - 1)
st[++nr] = make_pair(min(nod, *it), max(nod, *it));
min_level[nod] = min(min_level[nod], level[*it]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d\n", &n, &m);
int i, x, y;
for(i = 1; i <= m; i++)
{
scanf("%d %d\n", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);
printf("%d\n",comp);
for(int i = 1; i <= comp; i++)
{
for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}