Pagini recente » Cod sursa (job #385642) | Cod sursa (job #1048323) | Cod sursa (job #1072109) | Cod sursa (job #2269346) | Cod sursa (job #1883781)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
stack<int> st;
int lrez = 0;
vector<int> rez[100001];
vector<int> g[100001];
int viz[100001], low[100001];
int n, m;
void dfs(int nod, int tnod)
{
viz[nod] = viz[tnod] + 1;
low[nod] = viz[nod];
st.push(nod);
for (int i = 0; i < g[nod].size(); i++)
{
if (g[nod][i] != tnod)
{
if (!viz[g[nod][i]])
{
dfs(g[nod][i], nod);
low[nod] = min(low[nod], low[g[nod][i]]);
if (viz[nod] <= low[g[nod][i]])
{
while(!st.empty() && st.top() != g[nod][i])
{
rez[lrez].push_back(st.top());
st.pop();
}
rez[lrez].push_back(st.top());
st.pop();
rez[lrez].push_back(nod);
/*
while (lst > 0 && st[lst - 1] != g[nod][i])
{
lst--;
rez[lrez].push_back(st[lst]);
}
lst--;
rez[lrez].push_back(st[lst]);
rez[lrez].push_back(nod);*/
sort(rez[lrez].begin(), rez[lrez].end());
lrez++;
}
}
else low[nod] = min(low[nod], low[g[nod][i]]);
}
}
}
struct Pas { int nod, tnod; } pas[100001];
char post[100001];
int pc;
int mdfs(int nod, int tnod)
{
pc = 0;
pas[0].nod = nod;
pas[0].tnod = tnod;
viz[nod] = viz[tnod] + 1;
low[nod] = viz[nod];
st.push(nod);
while(pc >= 0)
{
nod = pas[pc].nod;
tnod = pas[pc].tnod;
if(post[pc])
{
post[pc] = 0;
int onod = pas[pc + 1].nod;
low[nod] = min(low[nod], low[onod]);
if (viz[nod] <= low[onod])
{
while(!st.empty() && st.top() != onod)
{
int t = st.top();
rez[lrez].push_back(st.top());
st.pop();
}
rez[lrez].push_back(st.top());
st.pop();
rez[lrez].push_back(nod);
sort(rez[lrez].begin(), rez[lrez].end());
lrez++;
}
}
else if(g[nod].size())
{
for(int i = g[nod].size() - 1; i >= 0; i--)
{
if(g[nod][i] != tnod)
{
if (!viz[g[nod][i]])
{
post[pc] = 1;
pc++;
pas[pc].nod = g[nod][i];
pas[pc].tnod = nod;
viz[g[nod][i]] = viz[nod] + 1;
low[g[nod][i]] = viz[g[nod][i]];
st.push(g[nod][i]);
g[nod].pop_back();
break;
}
else low[nod] = min(low[nod], low[g[nod][i]]);
}
g[nod].pop_back();
}
}
else pc--;
}
}
int main()
{
int a, b;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
if (!viz[i])
mdfs(i, 0);
}
printf("%d\n", lrez);
for (int i = 0; i < lrez; i++)
{
for (int j = 0; j < rez[i].size(); j++)
{
printf("%d ", rez[i][j]);
}
printf("\n");
}
return 0;
}