Pagini recente » creanga10-12 | Borderou de evaluare (job #2742458) | Borderou de evaluare (job #2017178) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #575375)
Cod sursa(job #575375)
#include<stdio.h>
#include<vector>
#define maxN 100005
using namespace std;
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
vector<int>G[maxN]; vector< pair<int,int> >Stv;
vector<int>CompB[maxN];
int i,m,n,Viz[maxN],x,y; int Vf,niv[maxN],lowest[maxN];
int Nrcomp,j;
inline void citire () {
fscanf(f,"%d %d",&n,&m);
for ( i = 1 ; i <= m ; ++i ){
fscanf(f,"%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void componenta (int nod,int fiu) {
int x,y;
++Nrcomp;
do{
x = Stv[Vf].first , y = Stv[Vf].second;
--Vf; Stv.pop_back();
CompB[Nrcomp].push_back(y);
}while ( x != nod && y != fiu );
CompB[Nrcomp].push_back(nod);
}
void dfs( int nod , int tata ) {
Viz[nod] = 1; lowest[nod] = niv[tata] + 1; niv[nod] = niv[tata] + 1;
for ( int i = 0 ; i < G[nod].size() ; ++i ){
int nodvcn = G[nod][i];
if ( nodvcn != tata ){
if ( !Viz[nodvcn] ){
++Vf;
Stv.push_back(make_pair(nod,nodvcn));
dfs(nodvcn,nod);
if ( lowest[nodvcn] >= niv[nod] )
componenta(nod,nodvcn);
if ( lowest[nodvcn] < lowest[nod] )
lowest[nod] = lowest[nodvcn];
}
else{
if ( lowest[nod] > niv[nodvcn] )
lowest[nod] = niv[nodvcn];
}
}
}
}
inline void afisare () {
vector<int>::iterator itt;
fprintf(g,"%d\n",Nrcomp);
for ( i = 1 ; i <= Nrcomp ; ++i ){
for ( itt = CompB[i].begin(); itt != CompB[i].end() ; ++itt ){
fprintf(g,"%d ",*itt);
}
fprintf(g,"\n");
}
}
int main () {
citire();
Vf = -1;
for ( i = 1 ; i <= n ; ++i ){
if ( !Viz[i] )
dfs(i,0);
}
afisare();
fclose(f);
fclose(g);
return 0;
}