Pagini recente » Cod sursa (job #1507360) | Cod sursa (job #194372) | Cod sursa (job #1608025) | Cod sursa (job #3160545) | Cod sursa (job #1520788)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005;
vector <int> g[nmax], comp[nmax], v;
stack <pair<int,int> > st;
int low[nmax], lev[nmax], tata[nmax], sol;
bool viz[nmax];
void get_sol(int x, int y)
{
int a, b;
sol++;
do
{
a=st.top().first;
b=st.top().second;
comp[sol].push_back(b);
st.pop();
} while(a!=x || b!=y);
comp[sol].push_back(a);
}
void dfs(int dad)
{
int i, son;
viz[dad]=true;
low[dad]=lev[dad];
for(i=0; i<g[dad].size(); i++)
{
son=g[dad][i];
if(!viz[son])
{
lev[son]=lev[dad]+1;
st.push(make_pair(dad, son));
dfs(son);
low[dad]=min(low[dad], low[son]);
if(low[son] >= lev[dad]) /// dad este nod critic
get_sol(dad, son);
}
else low[dad]=min(low[dad], lev[son]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m, x, y, i, j;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++)
{
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
lev[1]=1;
dfs(1);
printf("%d\n", sol);
for(i=1; i<=sol; i++)
{
sort(comp[i].begin(), comp[i].end());
for(j=0; j<comp[i].size(); j++)
printf("%d ", comp[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}