Cod sursa(job #2347194)

Utilizator Dragos123Tatar Dragos Vlad Dragos123 Data 18 februarie 2019 16:32:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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

const int MaxN = 100001;

int n, m;
std::vector<int> v[MaxN];
std::stack<int> st;

int low[MaxN];
int level[MaxN];
bool seen[MaxN];

std::vector<int> sol[MaxN];
int nrComponente;

void ReadData();
void DFS(int x);
void Solve();
void Write();

int main ()
{
    ReadData();
    Solve();
    Write();

    fin.close();
    fout.close();

    return 0;
}

void ReadData()
{
    fin >> n >> m;

    int x, y;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void DFS(int x)
{
    seen[x] = true;
    low[x] = level[x];
    st.push(x);

    for (size_t i = 0; i < v[x].size(); ++i)
    {
        int neigh = v[x][i];
        if (seen[neigh] == true)
        {
            low[x] = std::min(low[x], level[neigh]);
            continue;
        }

        level[neigh] = level[x] + 1;
        DFS(neigh);
        low[x] = std::min(low[x], low[neigh]);
        if (low[neigh] >= level[x])
        {
            nrComponente++;
            sol[nrComponente].push_back(x);
            int x = 0;
            do
            {
                x = st.top();
                st.pop();
                sol[nrComponente].push_back(x);
            } while(x != neigh);
        }
    }
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
    {
        if (!seen[i])
        {
            level[i] = 1;
            DFS(i);
        }
    }


}

void Write()
{
    fout << nrComponente << '\n';

     for (int i = 1; i <= nrComponente; i++)
    {
        for (size_t k = 0; k < sol[i].size(); k++)
        {
            fout << sol[i][k] << " ";
        }
        fout << "\n";
    }
}