Pagini recente » Cod sursa (job #185293) | Cod sursa (job #329387) | Cod sursa (job #2677257) | Cod sursa (job #720093) | Cod sursa (job #1478024)
#include <stdio.h>
#include <vector>
#include <bitset>
#include <set>
#define nmax 100010
using namespace std;
struct date { int x,y; };
int n,i,j,m,x,y,b,livmin[nmax],niv[nmax],tata[nmax];
vector <int> g[nmax];
bitset <nmax> fr;
vector < set<int> > sol;
set <int>::iterator it;
date stiva[nmax];
void desc_into_comp(int x,int y)
{
set <int> a;
do {
a.insert(stiva[b].x); a.insert(stiva[b].y); b--;
} while (stiva[b+1].x!=x || stiva[b+1].y!=y);
sol.push_back(a);
}
void dfs(int nod)
{
fr[nod]=1; livmin[nod]=niv[nod];
for (unsigned int i=0;i<g[nod].size();i++)
if (fr[g[nod][i]]==0) {
niv[g[nod][i]]=niv[nod]+1; tata[g[nod][i]]=nod;
b++; stiva[b].x=nod; stiva[b].y=g[nod][i];
dfs(g[nod][i]);
if (livmin[nod]>livmin[g[nod][i]]) livmin[nod]=livmin[g[nod][i]];
if (livmin[g[nod][i]]>=niv[nod]) desc_into_comp(nod,g[nod][i]);
} else
if (g[nod][i]!=tata[nod] && livmin[nod]>niv[g[nod][i]]) livmin[nod]=niv[g[nod][i]];
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
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);
}
for (i=1;i<=n;i++)
if (fr[i]==0) { niv[i]=1; dfs(i); }
printf("%d\n",sol.size());
for (i=0;i<sol.size();i++) {
for (it=sol[i].begin();it!=sol[i].end();it++) printf("%d ",*it);
printf("\n");
}
return 0;
}