Cod sursa(job #2195444)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 16 aprilie 2018 13:36:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define NMAX 100010

using namespace std;

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

vector <int> G[NMAX];
stack < pair <int, int> > Q;
vector < vector <int> > components;
vector <bool> visited;
vector <int> niv, nivmin;

void biconnected_component(int x, int y) {
    int a, b;
    components.push_back(vector<int>());
    do {
        a = Q.top().first;
        b = Q.top().second;
        Q.pop();
        components.back().push_back(b);
    } while(a != x or b != y);
    components.back().push_back(x);
}

void DFS(int x, int level) {
    niv[x] = nivmin[x] = level;
    visited[x] = true;
    for (vector <int> :: iterator it = G[x].begin(); it != G[x].end(); ++it) {
        if (visited[(*it)] == false) {
            Q.push(make_pair(x, (*it)));
            DFS((*it), level + 1);
            nivmin[x] = min(nivmin[x], nivmin[(*it)]);
            if (nivmin[(*it)] >= niv[x]) {
                biconnected_component(x, (*it));
            }
        }
        else {
            nivmin[x] = min(nivmin[x], niv[(*it)]);
        }
    }
}

int main() {
    int N, M;
    fin >> N >> M;
    for (int x, y, i = 0; i < M; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    visited.resize(N + 1, false);
    niv.resize(N + 1);
    nivmin.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        if (visited[i] == false) {
            DFS(i, 0);
        }
    }
    fout << components.size() << '\n';
    for (int i = 0; i < components.size(); ++i) {
        for (auto it = components[i].begin(); it != components[i].end(); ++it) {
            fout << *it << ' ';
        }
        fout << '\n';
    }
    return 0;
}