Pagini recente » Cod sursa (job #3235770) | Cod sursa (job #1141089) | Cod sursa (job #494505) | Cod sursa (job #3250900) | Cod sursa (job #1620324)
#include<cstdio>
#include<vector>
#include<set>
#include<stack>
using namespace std;
vector<int>L[100100];
set<int>S[200100];
stack< pair<int,int> >q;
int n,m,i,j,a,b,nr,v[100100],niv[100100],low[100100];
FILE *f,*g;
int minim(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int nod,int nv,int tata){
v[nod] = 1;
niv[nod] = low[nod] = nv;
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] , nv + 1 , nod );
low[nod] = minim( low[nod] , low[ L[nod][i] ] );
if( low[ L[nod][i] ] >= niv[nod] ){
nr++;
do{
a=q.top().first;
b=q.top().second;
q.pop();
S[nr].insert(a);
S[nr].insert(b);
}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])
dfs(i,1,0);
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
while( !S[i].empty() ){
fprintf(g,"%d ",*S[i].begin());
S[i].erase( S[i].begin() );
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}