Pagini recente » Cod sursa (job #2082685) | Cod sursa (job #3229064) | Cod sursa (job #2150938) | Cod sursa (job #2626645) | Cod sursa (job #1535462)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define NMAX 100000
vector<int> G[NMAX+10], dad, low, disc;
vector<vector<int> > rasp;
stack<pair<int, int> > st;
int cr, tm=1, last=0, cn;
void pop(pair<int,int> x)
{
pair<int,int> debug;
vector<int> tmp;
rasp.push_back(tmp);
while(st.top().first!=x.first||st.top().second!=x.second)
{
rasp[last].push_back(st.top().first);
rasp[last].push_back(st.top().second);
st.pop();
}
rasp[last].push_back(st.top().first);
rasp[last].push_back(st.top().second);
st.pop();
last++;
}
void dfs(int u)
{
int i,v;
low[u]=tm;
disc[u]=tm;
tm++;
for(i=0;i<G[u].size(); i++)
{
v=G[u][i];
if(!disc[v])
{
st.push(make_pair(u, v));
dad[v]=u;
dfs(v);
if(low[v]<low[u])
low[u]=low[v];
if(low[v]>=disc[u])
pop(make_pair(u,v));
}
else if(v!=dad[u])
low[u]=min(low[u], disc[v]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out","w", stdout);
int n, m, u, v, i;
scanf("%d%d", &n, &m);
cn=n;
for(i=1; i<=m; i++)
{
scanf("%d%d", &u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dad.assign(n+1, 0);
low.assign(n+1, 0);
disc.assign(n+1, 0);
dfs(1);
printf("%d\n", last);
int j;
for(i=0; i<last; i++)
{
sort(rasp[i].begin(), rasp[i].end());
printf("%d ", rasp[i][0]);
for(j=1; j<rasp[i].size(); j++)
if(rasp[i][j]!=rasp[i][j-1])
printf("%d ", rasp[i][j]);
printf("\n");
}
return 0;
}