Cod sursa(job #1621785)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 29 februarie 2016 21:41:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector <int> L[DIM],B[DIM],low(DIM),niv(DIM);
bitset <DIM> viz;
stack <int> Stack;

int N,M,t,CBC,x;

void dfs(int nod,int tata){

    viz[nod] = 1;
    t++;
    low[nod]=niv[nod]=t;
    Stack.push(nod);
    for(int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if(nod!=tata){
            if(!viz[vecin]){
                dfs(vecin,nod);
                low[nod]=min(low[nod],low[vecin]);
                if(low[vecin] >= niv[nod]){
                    CBC++;
                    do{
                        int x=Stack.top();
                        Stack.pop();
                        B[CBC].push_back(x);
                        if(x==vecin)
                            break;
                    }while(x!=vecin);
                    B[CBC].push_back(nod);
                }
            }
            else
                low[nod]=min(low[nod],niv[vecin]);
        }
    }

    t--;
}

int main(){

    fin >> N >> M;

    while(M--){
        int x,y;
        fin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for(int i=1;i<=N;i++)
        if(!viz[i])
            dfs(i,0);

    fout << CBC << "\n";

    for(int i=1;i<=CBC;i++){
        for(int j=0;j<B[i].size();j++)
            fout << B[i][j] << " ";
        fout << "\n";
    }

    fin.close();fout.close();

    return 0;




}