Cod sursa(job #2204705)

Utilizator EclipseTepes Alexandru Eclipse Data 16 mai 2018 21:01:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#define dMAX 100000

using namespace std;

int p, n, m;
int x, y, r;
int counter;

vector<int> graf[dMAX + 2];
bool viz[dMAX + 2];
int d[dMAX + 2], L[dMAX + 2];

int myStack[dMAX + 2], h;

vector<int> componente[dMAX + 2];
int cindx;

vector<int> critice;
bool crit[dMAX + 2];
vector<pair<int, int> > muchii;

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

void DFS(int v, int pv) {
    int newV, u;
    viz[v] = true;
    myStack[++h] = v;
    d[v] = d[pv] + 1;
    L[v] = d[v];
    if (d[v] == 2) counter++;
    for (u = 0; u < graf[v].size(); u++) {
        newV = graf[v][u];
        if (newV != pv) {
            if (viz[newV]) {
                L[v] = min(d[newV], L[v]);
            } else {
                DFS(newV, v);
                L[v] = min(L[newV], L[v]);
                /// Cerinta 1
                if (L[newV] >= d[v]) {
                    cindx++;
                    componente[cindx].push_back(v);
                    while (myStack[h] != newV) {
                        componente[cindx].push_back(myStack[h--]);
                    }
                    componente[cindx].push_back(myStack[h--]);
                }
                /// Cerinta 2
                if (L[newV] >= d[v] && v != r) {
                    if (!crit[v])
                    critice.push_back(v), crit[v] = true;
                }
                /// Cerinta 3
                if (L[newV] > d[v]) {
                    muchii.push_back({v, newV});
                }
            }
        }
    }
}

int main()
{
    int i, j;
    //fin >> p;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    r = 1;
    DFS(1, 0);
    //if (p == 1) {
        fout << cindx << '\n';
        for (i = 1; i <= cindx; i++) {
            //fout << componente[i].size() << ' ';
            for (j = 0; j < componente[i].size(); j++) {
                fout << componente[i][j] << ' ';
            }
            fout << '\n';
        }
    /*} else if (p == 2) {
        if (counter > 1) critice.push_back(r);
        fout << critice.size() << '\n';
        for (i = 0; i < critice.size(); i++) fout << critice[i] << ' ';
    } else {
        fout << muchii.size() << '\n';
        for (i = 0; i < muchii.size(); i++) {
            fout << muchii[i].first << ' ' << muchii[i].second << '\n';
        }
    }*/
    return 0;
}