Pagini recente » Cod sursa (job #752388) | Cod sursa (job #3213210) | Cod sursa (job #1813419) | Cod sursa (job #905997) | Cod sursa (job #530300)
Cod sursa(job #530300)
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 100005
#define pb push_back
using namespace std;
int n, m, ncomp, k, niv [nmax], c [nmax], tata [nmax];
bool viz [nmax];
vector <int> g [nmax];
vector <int> comp [nmax];
pair <int, int> stiva [nmax];
void scan ()
{
int i, a, b;
scanf ("%d%d", &n, &m);
for (i=1; i <= m; ++i)
{
scanf ("%d%d", &a, &b);
g [a].pb (b);
g [b].pb (a);
}
}
inline int min (int a, int b)
{
if (a < b)
return a;
return b;
}
void dfs (int nod)
{
int i, fiu;
viz [nod]=true;
c [nod]=niv [nod];
for (i=0; i != g [nod].size (); ++i)
{
fiu=g [nod] [i];
if (viz [fiu])
{
if ((tata [fiu] != nod) && (niv [nod] > niv [fiu]))
{
c [nod]=min (c [nod], niv [fiu]);
stiva [++k]=make_pair (nod, fiu);
}
continue;
}
niv [fiu]=niv [nod]+1;
tata [fiu]=nod;
stiva [++k]=make_pair (nod, fiu);
dfs (fiu);
c [nod]=min (c [nod], c [fiu]);
if (c [fiu] >= niv [nod])
{
++ncomp;
while (stiva [k] != make_pair (nod, fiu))
{
comp [ncomp].push_back (stiva [k].first);
--k;
}
comp [ncomp].push_back (stiva [k+1].second);
comp [ncomp].push_back (nod);
comp [ncomp].push_back (fiu);
--k;
}
}
}
void print ()
{
int i;
vector <int> :: iterator it, j;
printf ("%d\n", ncomp);
for (i=1; i <= ncomp; ++i)
{
sort (comp [i].begin (), comp [i].end ());
it=unique (comp [i].begin (), comp [i].end ());
for (j=comp [i].begin (); j != it; ++j)
printf ("%d ", *j);
printf ("\n");
}
}
int main ()
{
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
scan ();
niv [1]=1;
dfs (1);
print ();
return 0;
}