Cod sursa(job #3245740)

Utilizator maryyMaria Ciutea maryy Data 30 septembrie 2024 13:45:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int nmax=1e5, mmax=2e5;
int n, m;
vector <int> graph[nmax+1];
vector <int> level(nmax+1, 0), min_acces_level(nmax+1, 0);
vector <vector<int>> component;
bitset <nmax+1> vis;
void read()
{
    int a, b;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}
stack <int> s;
int timp=0;
void dfs(int child, int parent)
{
    vis[child]=true;
    s.push(child);//nodurile in ordinea parcurgerii dfs
    //timp++;
    //level[child]=timp;
    level[child]=level[parent]+1;
    min_acces_level[child]=level[child];
    for(int neighbor_of_child:graph[child])
    {
        if(neighbor_of_child != parent)
        {
            if(vis[neighbor_of_child]==1)//muchie de intoarcere
            {
                if(min_acces_level[child] > level[neighbor_of_child])
                    min_acces_level[child] = level[neighbor_of_child];
            }
            else
            {
                dfs(neighbor_of_child, child);
                if(min_acces_level[child] > min_acces_level[neighbor_of_child])
                    min_acces_level[child] = min_acces_level[neighbor_of_child];

                //child are un vecin care are nivelul mai mic decat poate atinge el
                if(min_acces_level[neighbor_of_child] >= level[child])
                {
                    vector <int> curr;
                    //totul din stiva pana la acel vecin inclusiv este in aceeasi componenta conexa
                    while(!s.empty() && s.top() != neighbor_of_child)
                    {
                        curr.push_back(s.top());
                        s.pop();
                    }
                    if(!s.empty())
                        s.pop();
                    curr.push_back(neighbor_of_child);
                    curr.push_back(child);
                    component.push_back(curr);
                }
            }
        }
    }
}
void display()
{
    out<<component.size()<<'\n';
    for(int i=0; i<component.size(); i++)
    {
        for(int j=component[i].size()-1; j>=0; j--)
            out<<component[i][j]<<" ";
        out<<'\n';
    }
}
int main()
{
    read();
    dfs(1, 0);
    display();
}