Pagini recente » Cod sursa (job #704478) | Cod sursa (job #3253659) | Cod sursa (job #2603439) | Cod sursa (job #776116) | Cod sursa (job #915989)
Cod sursa(job #915989)
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100010
using namespace std;
const char IN[]="biconex.in",OUT[]="biconex.out";
int N,M;
vector<int> ad[NMax];
vector<vector<int> > C;
void make(int x,int y,stack<pair<int,int> > &st){
pair<int,int> p;
p.first=p.second=0;
vector<int> vec;
while (p.first!=x || p.second!=y){
p=st.top();st.pop();
vec.push_back(p.first);
vec.push_back(p.second);
}
C.push_back(vec);
}
void dfs(int x,int p=-1,int lv=0)
{
static stack<pair<int,int> > st;
static int idx[NMax],low[NMax];
static bool b[NMax];
if (b[x]) return;
int i,ct=0;
idx[x]=low[x]=lv;
b[x]=true;
for (i=0;i<(int)ad[x].size();++i)
{
if (ad[x][i]==p) continue;
if (!b[ad[x][i]])
{
st.push(make_pair(x,ad[x][i]));
dfs(ad[x][i],x,lv+1);
low[x]=min(low[x],low[ad[x][i]]);
if (low[ad[x][i]]>=idx[x])
make(x,ad[x][i],st);
}
else
low[x]=min(low[x],idx[ad[x][i]]);
}
}
int main()
{
int i,j,x,y;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&M);
for (i=1;i<=M;++i)
{
scanf("%d%d",&x,&y);
ad[x].push_back(y);
ad[y].push_back(x);
}
fclose(stdin);
dfs(1);
freopen(OUT,"w",stdout);
printf("%d\n",C.size());
for (i=0;i<(int)C.size();++i){
sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
for (j=0;j<(int)C[i].size();++j)
printf("%d ",C[i][j]);
printf("\n");
}
fclose(stdout);
return 0;
}