Cod sursa(job #1899637)

Utilizator jurjstyleJurj Andrei jurjstyle Data 2 martie 2017 20:50:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

int N, M;
vector <int> G[100002];
stack <pair<int,int>> St;
vector <vector<int>> Ans;
vector <bool> Viz;
vector <int> Length, Nivel;
set <int> Curent;
vector <int> Curent2;

void DFS(int, int, int);

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    Viz = vector <bool> (N + 1);
    Length = Nivel = vector <int> (N + 1);
    for (int i = 1; i <= N; ++i)
        if (Viz[i] == 0)
            DFS(i, 0, 1);
    g << Ans.size() << "\n";
    for (int i = 0; i < Ans.size(); ++i)
    {
        for (const int & x : Ans[i])
            g << x << " ";
        g << "\n";
    }
    f.close();
    g.close();
    return 0;

}
void DFS(int node, int tata, int nivel)
{
    Length[node] = Nivel[node] = nivel;
    Viz[node] = 1;
    for (const int & fiu : G[node])
    {
        if (tata == fiu)
            continue;
        if (Viz[fiu] == 0)
        {
            St.push({node, fiu});
            DFS(fiu, node, nivel + 1);
            Length[node] = min(Length[node], Length[fiu]);
            if (Length[fiu] >= Nivel[node])
            {
                Curent.clear();
                Curent2.clear();
                while (true)
                {
                    int x1 = St.top().first, x2 = St.top().second;
                    Curent.insert(x1);
                    Curent.insert(x2);
                    St.pop();
                    if (x1 == node && x2 == fiu)
                        break;
                }
                for (const int & x : Curent)
                    Curent2.push_back(x);
                Ans.push_back(Curent2);
            }
        }
        else
            Length[node] = min(Length[node], Nivel[fiu]);
    }
}