Cod sursa(job #2582315)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 16 martie 2020 16:28:38
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int NMax = 100000;

vector <int> g[NMax + 5], sol[NMax + 5];
stack <int> st;
int n, m, nr;
int level[NMax + 5], low[NMax + 5];
bool use[NMax + 5];

void Read(){
    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);
    }
}

void DFS(int node, int father){
    use[node] = 1;
    st.push(node);
    level[node] = low[node] = level[father] + 1;
    for (auto other : g[node]){
        if (other == father)
            continue;
        if (!use[other]){
            int aux = st.size();
            DFS(other, node);
            if (low[other] >= level[node]){
                ++nr;
                while (st.size() > aux){
                    int x = st.top();
                    st.pop();
                    sol[nr].push_back(x);
                }
                sol[nr].push_back(node);
            }
            low[node] = min(low[node], low[other]);
        }
        else
            low[node] = min(low[node], level[other]);
    }
}

void Print(){
    fout << nr << '\n';
    for (int i = 1; i <= nr; i++){
        sort(sol[i].begin(), sol[i].end());
        fout << sol[i][0] << ' ';
        for (int j = 1; j < sol[i].size(); j++)
            if (sol[i][j] != sol[i][j - 1])
                fout << sol[i][j] << ' ';
        fout << '\n';
    }
}

int main(){
    Read();
    DFS(1, 0);
    Print();
    return 0;
}