Pagini recente » Cod sursa (job #2766322) | Cod sursa (job #1674452) | Cod sursa (job #100513) | Cod sursa (job #722886) | Cod sursa (job #1686301)
#include <stdio.h>
#include <set>
#include <stack>
#include <cstring>
#include <vector>
#define nmax 100010
using namespace std;
int n,m,x,y,nr;
int livmin[nmax],tata[nmax],niv[nmax];
bool fr[nmax],b[nmax];
vector <int> g[nmax];
vector <set <int> > sol;
stack < pair<int,int> > st;
set <int> :: iterator it;
void desc_comp(int i,int j)
{
nr++; set <int> a;
while (1) {
int x=st.top().first,y=st.top().second; st.pop();
a.insert(x); a.insert(y);
if (x==i && y==j) break;
}
sol.push_back(a);
}
void dfs(int nod)
{
livmin[nod]=niv[nod]; fr[nod]=true;
for (int i=0;i<(int)g[nod].size();i++)
if (!fr[g[nod][i]]) {
st.push(make_pair(nod,g[nod][i]));
niv[g[nod][i]]=niv[nod]+1;
tata[g[nod][i]]=nod;
dfs(g[nod][i]);
livmin[nod]=min(livmin[nod],livmin[g[nod][i]]);
if (livmin[g[nod][i]]>=niv[nod]) desc_comp(nod,g[nod][i]);
} else
if (g[nod][i]!=tata[nod]) livmin[nod]=min(livmin[nod],niv[g[nod][i]]);
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++) {
scanf("%d %d",&x,&y);
g[x].push_back(y); g[y].push_back(x);
}
dfs(1);
printf("%d\n",sol.size());
for (int i=0;i<sol.size();i++,printf("\n"))
for (it=sol[i].begin();it!=sol[i].end();it++) printf("%d ",*it);
return 0;
}