Cod sursa(job #1147852)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 20 martie 2014 10:49:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define DIMN 100100
#define DIMM 200100
using namespace std;

vector<int> L[DIMN];
stack < pair<int, int>  > s;
pair<int,int> p;
vector< int > C[DIMM];

int Niv[DIMN],Low[DIMN],i,j,n,m,x,y,cb;
ifstream fin("biconex.in");
ofstream fout("biconex.out");


void dfs(int nod, int parent, int niv) {
    Niv[nod] = niv;
    Low[nod] = niv;

    for (int i=0; i<L[nod].size(); i++) {
        if (L[nod][i] == parent)
                continue;
        if (Niv[  L[nod][i]  ] == 0) {
            // cand inaintez pun in stiva muchiile de avansare
            s.push( make_pair(nod, L[nod][i]   )  );
            // fiecare pornire cu autoapel intr-un fiu poate provoca o componenta biconexa generata de muchia pe care pornesc
            dfs(L[nod][i], nod, niv+1);
            // daca la intoarcerea din autoapelul pe aceasta muchie nu am coborat sub nivelul nodului curent inseamna ca muchia pe care tocmai am terminat genereaza o cb
            if (Niv[nod] <= Low[  L[nod][i]  ]    ) {
                // scot din stiva pana intalnesc aceasta muchie nod, L[nod][i]
                // componanta biconexa are ca si noduri extremitatile muchiilor puse in stiva dupa muchia ce a generat-o deci scot din stiva pana intalnesc acea muchuie
                cb++;
                do {
                    p = s.top();
                    s.pop();
                    C[cb].push_back(p.first);
                    C[cb].push_back(p.second);
                } while (p.first != nod || p.second!=L[nod][i]);
            }
        }
        Low[nod] = min (Low[nod], Low[  L[nod][i]  ]);
    }
}


int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }



    for (i=1;i<=n;i++)
        if (Niv[i] == 0) {
            dfs(i, 0, 1);
        }

    fout<<cb<<"\n";
    for (i=1;i<=cb; i++) {
        sort(C[i].begin(), C[i].end());
        fout<<C[i][0]<<" ";
        for (j=1; j<C[i].size(); j++)
            if (C[i][j] != C[i][j-1])
                fout<<C[i][j]<<" ";
        fout<<"\n";
    }

    return 0;
}