Pagini recente » Cod sursa (job #350503) | Cod sursa (job #856663) | Cod sursa (job #1889683) | Cod sursa (job #1454429) | Cod sursa (job #1411150)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
int N, M, dp[100009], niv[100009];
vector < int > v[100009];
vector < vector < int > > answer;
stack < pair < int , int > > S;
void unific (vector < int > &v)
{
sort (v.begin(), v.end ());
v.erase (unique (v.begin(), v.end()), v.end ());
}
void Add_Component (pair < int , int > stop)
{
vector < int > comp;
pair < int , int > top;
do
{
top = S.top ();
S.pop ();
comp.push_back (top.first);
comp.push_back (top.second);
}while (top != stop);
unific (comp);
answer.push_back (comp);
}
void dfs (int nod, int tata)
{
dp[nod] = niv[nod];
for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
if (niv[*it] == -1)
{
niv[*it] = niv[nod] + 1;
S.push (make_pair (nod, *it));
dfs (*it, nod);
if (dp[*it] > niv[nod])
;////muchie critica
if (dp[*it] >= niv[nod])
Add_Component (make_pair (nod, *it));////nod e critic
}
bool already_once = 0;
for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
{
if (*it == nod && already_once == 0)
already_once = 1;
else
dp[nod] = min (dp[nod], dp[*it]);
}
}
void Print ()
{
printf ("%d\n", answer.size ());
for (int i=0; i<answer.size (); i++, printf ("\n"))
for (vector < int > :: iterator it = answer[i].begin(); it != answer[i].end(); it ++)
printf ("%d ", *it);
}
int main ()
{
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
scanf ("%d %d", &N, &M);
while (M)
{
M --;
int x, y;
scanf ("%d %d", &x, &y);
v[x].push_back (y);
v[y].push_back (x);
}
for (int i=1; i<=N; i++)
niv[i] = -1;
dfs (1, 0);
Print ();
return 0;
}