Cod sursa(job #1340509)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 11 februarie 2015 21:12:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#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;
}