Cod sursa(job #2084362)

Utilizator amaliarebAmalia Rebegea amaliareb Data 9 decembrie 2017 00:09:08
Problema Componente biconexe Scor 42
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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, viz[MaxN], low[MaxN], k, nrc, fr[MaxN];
vector<int> gr[MaxN], comp[MaxN];
stack<pair<int, int> > st;

void dfs(int node, int fth)
{
    viz[node] = ++k;
    low[node] = viz[node];
    for (auto y: gr[node])
        if(!viz[y])
        {
            dfs(y, node);
            low[node] = min(low[node], low[y]);
            if (low[y] >= viz[node])
            {
                memset(fr, 0, sizeof(fr));
                ++nrc;
                while (!st.empty())
                {
                    if (!fr[st.top().first]) fr[st.top().first] = 1, comp[nrc].push_back(st.top().first);
                    if (!fr[st.top().second]) fr[st.top().second] = 1, comp[nrc].push_back(st.top().second);
                    st.pop();
                }
            }
        }
        else if(y != fth) low[node] = min(low[node], viz[y]);
    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);
    }
    int startt = 1;
    while (gr[startt].size() <= 1) startt++;
    dfs(startt, 0);
    g << nrc << '\n';
    for (int i = 1; i <= nrc; i++)
    {
        for (auto j: comp[i]) g << j << ' ';
        g << '\n';
    }
    return 0;
}