Cod sursa(job #1863812)

Utilizator DobosDobos Paul Dobos Data 31 ianuarie 2017 11:06:10
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

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

int low[NMAX],level[NMAX];
stack < pair < int ,int > > S;
vector < int > G[NMAX];
vector < map < int, bool > > V;
map < int, bool> aux;


void Addcomponent(int x,int y){
    aux.clear();
    int a,b;
    do{
        a = (S.top()).first;
        b = (S.top()).second;
        S.pop();

        aux[a] = 1;
        aux[b] = 1;
    }while(x != a || y  != b);

    V.push_back(aux);
}


void DFS(int nod,int lvl){
    low[nod] = level[nod] = lvl;

    for(auto const &i : G[nod]){
        if(low[i] == 0){
            S.push({nod,i});
            DFS(i,lvl + 1);
            low[nod] = min(low[nod],low[i]);
            if(low[i] >= level[nod])
                Addcomponent(nod,i);
        } else {
            low[nod] = min(low[nod],level[i]);
        }
    }



}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m,x,y;

    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    DFS(1,1);
    fout << V.size() << "\n";
    for(auto const &i : V){
        for(auto const &j : i)
            fout << j.first << " ";
        fout << "\n";
        }
    return 0;
}