Pagini recente » Cod sursa (job #1241186) | Cod sursa (job #1796608) | Cod sursa (job #502344) | Cod sursa (job #562821) | Cod sursa (job #567170)
Cod sursa(job #567170)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
using namespace std;
vector<int> a[100001];
stack< pair<int,int> > s;
int n,m,step=0,fii=0,nrcomp;
vector<int> dfn(100001,-1);
vector<int> low(100001,-1);
vector< set<int> > sol;
void readData(){
int i,x,y;
freopen("biconex.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=0;i<m;++i){
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
}
void buildSet(int nr,int x,int y){
pair<int,int> p,t;
set<int> cur;
p=make_pair(x,y);
do{
t=s.top();
s.pop();
cur.insert(t.first);
cur.insert(t.second);
}while(t!=p);
sol.push_back(cur);
}
void biconex(int x,int tx){
int i,y;
dfn[x]=low[x]=++step;
for(i=0;i<a[x].size();++i){
y=a[x][i];
if(y!=tx && dfn[y]<dfn[x])
s.push(make_pair(x,y));
if(dfn[y]==-1){
biconex(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
// printf("%d %d,",x,y);
buildSet(nrcomp,x,y);
nrcomp++;
}
}
else if(y!=tx)
low[x]=min(low[x],dfn[y]);
}
}
void writeComp(){
set<int>::iterator it;
int i;
for(i=0;i<nrcomp;++i){
for(it=sol[i].begin();it!=sol[i].end();++it)
printf("%d ",*it);
printf("\n");
}
}
int main(){
readData();
freopen("biconex.out","w",stdout);
biconex(1,-1);
printf("%d\n",nrcomp);
writeComp();
return 0;
}