Pagini recente » Cod sursa (job #1909233) | Cod sursa (job #2361137) | Cod sursa (job #2419658) | Cod sursa (job #1686239) | Cod sursa (job #1920925)
#include <bits/stdc++.h>
#define nmax 200001
using namespace std;
int n, m;
vector <int> v[nmax];
int dfn[nmax], low[nmax], num;
vector <pair <int, int> > s;
set <int> sol[nmax];
int q;
void init()
{
int i;
for (i=1; i<=n; ++i) dfn[i]=low[i]=-1;
s.push_back(make_pair(1,-1));
}
void afis(int x, int u)
{
q++;
int tmp1, tmp2;
do
{
tmp1=s.back().first;
tmp2=s.back().second;
s.pop_back();
sol[q].insert(tmp1); sol[q].insert(tmp2); }
while (tmp1!=x || tmp2!=u);
}
void biconex (int u, int tu)
{
int x, i;
dfn[u]=low[u]=++num;
vector <int> :: iterator it;
for (it=v[u].begin();it!=v[u].end();++it)
{
x=(*it);
if (x!=tu && dfn[x] < dfn[u])
s.push_back(make_pair(x,u));
if (dfn[x]==-1) {
biconex(x,u);
low[u]=min(low[u],low[x]);
if (low[x] >= dfn[u])
afis(x,u);
}
else if (x!=tu)
{
low[u]=min(low[u],dfn[x]);
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int m, x, y, i;
f >> n >> m;
for (i=1; i<=m; ++i)
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
init();
biconex(1,-1);
g << q << "\n";
for (i=1; i<=q; ++i)
{
for (set <int> :: iterator it=sol[i].begin();it!=sol[i].end();++it)
g << *it << " ";
g <<"\n";
}
return 0;
}