Cod sursa(job #2084376)

Utilizator amaliarebAmalia Rebegea amaliareb Data 9 decembrie 2017 00:32:15
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int MaxN = 100005;
int n, m, lev[MaxN], low[MaxN], k, nrc, fr[MaxN];
vector<int> gr[MaxN], comp[MaxN];
stack<pair<int, int> > st;

inline  void make_comp(int node)
{
    ++nrc;
    while (!st.empty())
    {
        comp[nrc].push_back(st.top().first);
        st.pop();
    }
    comp[nrc].push_back(node);
}

void dfs(int node, int fth)
{
    lev[node] = low[node] = lev[fth] + 1;
    for (auto son: gr[node])
        if (!lev[son])
        {
            dfs(son, node);
            low[node] = min(low[node], low[son]);
            if (low[son] >= lev[node])
            {
                make_comp(node);
            }
        }
        else if (lev[son] < lev[node] - 1) low[node] = min(low[node], lev[son]);
    if (fth > 0) st.push({node, fth});
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!lev[i]) dfs(i, 0);
    g << nrc << '\n';
    for (int i = 1; i <= nrc; i++)
    {
        for (auto j: comp[i]) g << j << ' ';
        g << '\n';
    }
    return 0;
}