Cod sursa(job #2701089)

Utilizator codruta.miron08Miron Ioana Codruta codruta.miron08 Data 29 ianuarie 2021 19:55:40
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
bool viz[100005];
vector<int> nodes[100005];
vector <vector <int> > rez;
stack <pair <int, int > > edges;
int n, m, depth[100005], lowlink[100005],index = 1;
void solve(pair<int, int > edge)
{
    vector <int> vec;
    int k = 0;
    int ok = 1;
    while(ok)
    {
        pair < int , int > vf = edges.top();
        edges.pop();
        vec.push_back(vf.first);
        vec.push_back(vf.second);
        if(vf == edge)
            break;
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    rez.push_back(vec);
        vec.clear();
}
void dfs(int node, int parent){

    depth[node] = depth[parent] + 1;
    lowlink[node] = depth[node];
    viz[node] = true;
    for(auto &it:nodes[node]){
        if(it == parent)
            continue;
            if(!viz[it])
            {
                edges.push({node, it});
            dfs(it, node);
            lowlink[node] = min(lowlink[it], lowlink[node]);
            if(lowlink[it] >= depth[node])
            solve({node,it});
            }
            else
            lowlink[node] = min(lowlink[node], depth[it]);

    }
}
int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        nodes[x].push_back(y);
        nodes[y].push_back(x);
    }
   dfs(1,0);
     fout << rez.size() << "\n";
     for( auto &it : rez)
     {
         for(auto &v: it)
            fout << v << " ";
         fout << "\n";
     }
    return 0;
}