Cod sursa(job #1923340)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 10 martie 2017 22:44:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100000 + 5;
const int MMAX = 2 * NMAX;

struct Edge {
    int a, b;
    Edge(int _a = 0, int _b = 0):
        a(_a), b(_b) {}
    inline int other(int node) {
        return a ^ b ^ node;
    }
} edges[MMAX];

int N, M;
vector <int> graph[NMAX];

bool vis[NMAX];
int h[NMAX];
int low[NMAX];

stack <int> stk;

vector <vector <int> > bicos;
void extract(int edg) {
    vector <int> sol;
    while (stk.top() != edg) {
        sol.push_back(edges[stk.top()].a);
        sol.push_back(edges[stk.top()].b);
        stk.pop();
    }
    sol.push_back(edges[stk.top()].a);
    sol.push_back(edges[stk.top()].b);
    stk.pop();

    bicos.push_back(sol);
}

void dfs(int node) {
    vis[node] = true;
    for (auto it: graph[node]) {
        int son = edges[it].other(node);
        if (!vis[son]) {
            h[son] = low[son] = h[node] + 1;
            stk.push(it);
            dfs(son);

            if (low[son] >= h[node])
                extract(it);
            else if (low[son] < low[node])
                low[node] = low[son];
        }
        else {
            if (h[son] < low[node])
                low[node] = h[son];
         }
    }
}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    cin >> N >> M;
    for (int i = 1; i <= M; ++ i) {
        int a, b;
        cin >> a >> b;
        edges[i].a = a, edges[i].b = b;
        graph[a].push_back(i);
        graph[b].push_back(i);
    }

    for (int i = 1; i <= N; ++ i)
        if (!vis[i])
            dfs(i);

    cout << bicos.size() << '\n';
    for (auto &it: bicos) {
        sort(it.begin(), it.end());
        it.resize(unique(it.begin(), it.end()) - it.begin());
        for (int i = 0; i < it.size(); ++ i)
            cout << it[i] << " \n"[i + 1 == it.size()];
    }
    return 0;
}