Cod sursa(job #2668648)

Utilizator dumitru123Patularu Mihai dumitru123 Data 5 noiembrie 2020 06:55:59
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

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

const int NMAX = 1e5+5;
vector<int> graf[NMAX];
int niv[NMAX], low[NMAX];
bool vis[NMAX], use[NMAX];
vector<vector<int> > sol;
stack<pair<int,int> > Edges;

void CompBiconexa(int x, int y) {
    vector<int> c;
    pair<int,int> m, m1 = make_pair(x, y), m2 = make_pair(y, x);
    do {
        m = Edges.top();
        c.push_back(m.first);
        c.push_back(m.second);
        Edges.pop();
    } while(m != m1 && m != m2);
    sol.push_back(c);
}

void dfs(int nod, int tata) {
    vis[nod] = 1;
    low[nod] = niv[nod];
    for(int i = 0; i < (int)graf[nod].size(); i++) {
        int next = graf[nod][i];
        if(next != tata && niv[nod] > niv[next]) {
            Edges.push(make_pair(next, nod));
        }
        if(!vis[next]) {
            niv[next] = niv[nod] + 1;
            dfs(next, nod);
            low[nod] = min(low[nod], low[next]);
            if(low[next] >= niv[nod]) {
                CompBiconexa(next, nod);
            }
        } else {
            if(next != tata && low[nod] > niv[next]) {
                low[nod] = niv[next];
            }
        }
    }
}
int main()
{
    int n, m;
    f >> n >> m;
    while(m--) {
        int x, y;
        f >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    niv[1] = 1;
    dfs(1, 0);
    g << sol.size() << '\n';
    for(int i = 0 ; i < (int)sol.size(); i++) {
        for(int j = 0; j < (int)sol[i].size(); j++) {
            use[sol[i][j]] = 1;
        }
        for(int j = 0; j < (int)sol[i].size(); j++) {
            if(use[sol[i][j]] == 1) {
                g << sol[i][j] << ' ';
                use[sol[i][j]] = 0;
            }
        }
        g << '\n';
    }
    return 0;
}