Pagini recente » Cod sursa (job #1019576) | Cod sursa (job #2876954) | Cod sursa (job #2372759) | Cod sursa (job #743717) | Cod sursa (job #1535194)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
#define NMAX 100000
vector<int> G[NMAX+10], dad, low, disc;
vector<vector<int> > rasp;
stack<pair<int, int> > st;
vector<int> freq;
int cr,time=1, last=0, cn;
void pop(pair<int,int> x)
{
int i;
vector<int> tmp;
rasp.push_back(tmp);
freq.assign(cn+1, 0);
while(st.top().first!=x.first||st.top().second!=x.second)
{
freq[st.top().first]=1;
freq[st.top().second]=1;
st.pop();
}
freq[st.top().first]=1;
freq[st.top().second]=1;
st.pop();
for(i=1; i<=cn;i++)
if(freq[i])
rasp[last].push_back(i);
last++;
}
void dfs(int u)
{
int i,v;
low[u]=time;
disc[u]=time;
time++;
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++)
{
for(j=0; j<rasp[i].size(); j++)
printf("%d ", rasp[i][j]);
printf("\n");
}
return 0;
}