Cod sursa(job #2268215)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 24 octombrie 2018 16:35:57
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

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

vector<int> v[N];
vector< vector<int> > rez;
stack<int> st;
bool viz[N];
int lvl[N],low[N];

void dfs(int x)
{
    viz[x] = 1;
    st.push(x);
    for (auto it: v[x])
        if (!viz[it])
        {
            lvl[it] = low[it] = lvl[x]+1;
            dfs(it);
            if (low[it]>=lvl[x])
            {
                vector<int> t;
                while (st.top()!=it)
                {
                    t.push_back(st.top());
                    st.pop();
                }
                st.pop();
                t.push_back(it);
                t.push_back(x);
                rez.push_back(t);
            }
            low[x] = min(low[x],low[it]);
        }
        else
            low[x] = min(low[x],lvl[it]);
}

int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i<=n; i++)
        if (!viz[i])
            dfs(i);
    out << rez.size() << "\n";
    for (auto a: rez)
    {
        sort(a.begin(),a.end());
        for (auto b: a)
            out << b << " ";
        out << "\n";
    }
}