Cod sursa(job #990972)

Utilizator 2dorTudor Ciurca 2dor Data 29 august 2013 13:05:44
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int MAXN = 100005;
const int INF = 0x3f3f3f;
int a, b, n, m;

stack<pair<int, int> > stiva;
vector<vector<int> > matr;

struct graph {
    vector<int> vecini;
    int nivel;
    int low;
}nods[MAXN];

void read() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> a >> b;
        nods[a].vecini.push_back(b);
        nods[b].vecini.push_back(a);
    }
}

void extra_biconnex(int a, int b) {
    vector<int> aux;
    int x, y;
    do {
        x = stiva.top().first;
        y = stiva.top().second;
        stiva.pop();
        aux.push_back(x);
        aux.push_back(y);
    }while (x != a || y != b);
    matr.push_back(aux);//salvez componenta biconexa intr-o matrice
}

void dfs(int node, int father, int level) {
    vector<int>::iterator it;
    nods[node].nivel = nods[node].low = level;//marchez la ce nivel sunt, deci si ca am vizitat nodul 'node'
    for (it = nods[node].vecini.begin(); it != nods[node].vecini.end(); ++it) {
        if (*it == father) continue;//daca avem de a face cu tatal nodului, sarim
        if (nods[*it].nivel == -1) {//daca vecinul *it nu a fost vizitat
            stiva.push(make_pair(node, *it));//bag muchia in stiva
            dfs(*it, node, level + 1);//continui DFS-ul cu vecinul *it al lui 'node'
            nods[node].low = min(nods[node].low, nods[*it].low);//daca *it a gasit un nivel minim mai mic, salvam
            if (nods[node].nivel <= nods[*it].low)
                extra_biconnex(node, *it);
        }else
            nods[node].low = min(nods[node].low, nods[*it].nivel);
    }
}

void write() {
    fout << matr.size() << '\n';//nr componente biconexe
    for (unsigned i = 0; i < matr.size(); ++i) {
        sort(matr[i].begin(), matr[i].end());//sortam
        matr[i].push_back(matr[i][matr[i].size() - 1]);
        for (unsigned j = 0; j < matr[i].size(); j += 2) {
            fout << matr[i][j] << ' ';
        }
        fout << '\n';
    }
}

int main(){
    read();
    for (int i = 0; i <= n; ++i)
        nods[i].nivel = -1;//in nodurile cu -1 nu am fost inca; la inceput nu am fost in niciun nod
    dfs(1, 0, 1);
    write();
    fin.close();
    fout.close();
    return 0;
}