Cod sursa(job #2149587)

Utilizator remus88Neatu Remus Mihai remus88 Data 2 martie 2018 19:14:54
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#define Nmax 100009

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

typedef pair <int, int> edge;
#define x first
#define y second

int n,m,x,y,low[Nmax],found[Nmax],cnt,parent[Nmax];
vector <int> G[Nmax],v,sol;
vector <vector <int>> BiconexComponents;
stack <edge> S;

void ReadInput() {

    f>>n>>m;
    for (int i=1; i<=m; ++i) {

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

void getBCC(edge E) {

    edge aux;
    v.clear();
    do {
        aux=S.top();
        S.pop();
      //  g<<aux.x<<' '<<aux.y<<'\n';
        v.push_back(aux.x);
        v.push_back(aux.y);

    } while (aux!=E);

    sort(v.begin(), v.end());
    auto it = unique(v.begin(), v.end());
    v.erase(it, v.end());

    BiconexComponents.push_back(v);

}

void DFS(int node) {

    ++cnt;
    found[node]=cnt;
    low[node]=cnt;

    for (auto x: G[node]) {

        if (!parent[x]) {

            S.push(edge(node,x));
            parent[x]=node;
            DFS(x);

            low[node]=min(low[node],low[x]);

            if (low[x]>=found[node]) getBCC(edge(node,x));
        }
        else if (parent[node]!=x) low[node]=min(low[node],found[x]);
    }

}

void Tarjan() {

    for (int i=1; i<=n; ++i)
        if (!parent[i]) {

            parent[i]=i;
            DFS(i);
        }

    /*for (int i=1; i<=n; ++i) g<<found[i]<<' ';
    g<<'\n';

    for (int i=1; i<=n; ++i) g<<low[i]<<' ';
    g<<'\n';

    for (int i=1; i<=n; ++i) g<<parent[i]<<' ';
    g<<'\n';*/
}

void WriteOutput() {

    g<<BiconexComponents.size()<<'\n';
    for (auto x: BiconexComponents) {

        for (auto y: x) g<<y<<' ';
        g<<'\n';
    }
}

void Solve() {

    Tarjan();
}

int main() {

    ReadInput();
    Solve();
    WriteOutput();

    f.close(); g.close();
    return 0;
}