Pagini recente » Cod sursa (job #2068793) | Cod sursa (job #1235991) | Cod sursa (job #1716420) | Cod sursa (job #1236104) | Cod sursa (job #1474917)
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
#define nmax 100010
using namespace std;
struct date { int x,y; };
int x,y,n,m,i,j,nr,k,livmin[nmax],niv[nmax],tata[nmax],b;
bitset <nmax> fr;
vector <int> g[nmax];
vector <vector<pair<int,int> > > sol;
date stiva[nmax];
void desc_into_comp(int x,int y)
{
vector <pair<int,int> > a; a.clear();
if (x>y) swap(x,y);
do {
a.push_back(make_pair(stiva[b].x,stiva[b].y)); b--;
} while (b>0 && (stiva[b+1].x!=x || stiva[b+1].y!=y));
sol.push_back(a);
}
void dfs(int x)
{
unsigned int i; livmin[x]=niv[x]; fr[x]=1;
for (i=0;i<g[x].size();i++) {
if (fr[g[x][i]]==0) {
niv[g[x][i]]=niv[x]+1; tata[g[x][i]]=x;
b++; stiva[b].x=x; stiva[b].y=g[x][i];
if (x==i) nr++;
dfs(g[x][i]);
if (livmin[x]>livmin[g[x][i]]) livmin[x]=livmin[g[x][i]];
if (livmin[g[x][i]]>=niv[x]) desc_into_comp(g[x][i],x);
} else
if (g[x][i]!=tata[x] && livmin[x]>niv[g[x][i]]) livmin[x]=niv[g[x][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) { k++; nr=0; niv[i]=1; dfs(i); }
printf("%d\n",sol.size());
for (i=0;i<sol.size();i++) {
set <int> a; a.clear(); set <int>::iterator it;
for (j=0;j<sol[i].size();j++) a.insert(sol[i][j].first),a.insert(sol[i][j].second);
for (it=a.begin();it!=a.end();it++) printf("%d ",*it);
printf("\n");
}
return 0;
}