Cod sursa(job #1620324)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 29 februarie 2016 01:35:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#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;
}