Pagini recente » Cod sursa (job #2270172) | Cod sursa (job #1002282) | Cod sursa (job #1616437) | Cod sursa (job #3255547) | Cod sursa (job #1340509)
#include<cstdio>
#include<vector>
#include<set>
#include<stack>
using namespace std;
vector<int>L[100100];
set<int>S[200100];
set<int>::iterator it;
stack< pair<int,int> >q;
int n,m,i,j,a,b,nr,v[100100],nv[100100],low[100100];
FILE *f,*g;
int minim(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int nod,int niv,int tata){
v[nod]=1;
nv[nod]=low[nod]=niv;
for(int i=0;i<L[nod].size();i++){
if(L[nod][i]==tata)
continue;
if(v[ L[nod][i] ]==0){
q.push(make_pair(nod,L[nod][i]));
dfs(L[nod][i],niv+1,nod);
low[nod]=minim(low[nod],low[ L[nod][i] ]);
if(low[ L[nod][i] ]>=nv[nod]){
nr++;
do{
a=q.top().first;
b=q.top().second;
S[nr].insert(a);
S[nr].insert(b);
q.pop();
}while(a!=nod && b != L[nod][i]);
}
}
else
low[nod]=minim(low[nod],low[ L[nod][i] ]);
}
}
int main(){
f=fopen("biconex.in","r");
g=fopen("biconex.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
L[a].push_back(b);
L[b].push_back(a);
}
for(i=1;i<=n;i++){
if(v[i]==0){
dfs(i,1,0);
}
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
while(!S[i].empty()){
it=S[i].begin();
fprintf(g,"%d ",*it);
S[i].erase(it);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}