Cod sursa(job #1862255)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 29 ianuarie 2017 18:02:33
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e5 + 5;

vector < int > G[NMax];
stack < int > Stack;
vector < vector < int > > Ans;

int level[NMax];
int low[NMax];

inline void AddComponent(const int &node) {
    vector < int > aux;

    while(Stack.top() != node) {
        aux.push_back(Stack.top());
        Stack.pop();
    }
    aux.push_back(node);
    Ans.push_back(aux);
}

void DFS(const int &node, const int &lvl) {
    Stack.push(node);

    level[node] = low[node] = lvl;
    for(auto const &i: G[node]) {
        if(level[i] == 0) {
            DFS(i, lvl + 1);
            low[node] = min(low[node], low[i]);
            if(low[i] >= level[node]) {
                AddComponent(node);
            }
        } else {
            low[node] = min(low[node], level[i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;

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

    DFS(1, 1);

    fout << Ans.size() << "\n";
    for(auto i: Ans) {
        sort(i.begin(), i.end());
        for(auto const &j: i) {
            fout << j << " ";
        }

        fout << "\n";
    }

    return 0;
}