Cod sursa(job #2442961)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 25 iulie 2019 21:24:21
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <iostream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <queue>

using namespace std;

ifstream fin ("dmax.in");
ofstream fout ("dmax.out");

vector <int> a[100005];
vector <vector <int> > e;
unordered_set <int> cutVertex;
queue <int> q;
int d[100005], f[100005], disc[100005], low[100005], parent[100005], sz, temp;
pair <int, int> cutEdges[200005];
stack <pair <int, int> > st;
void found(int x, int y)
{
    pair <int, int> top;
    vector <int> b;
    do {
        top.first = st.top().first, top.second = st.top().second;
        st.pop();
        b.push_back(top.first); b.push_back(top.second);
    }
    while(top.first != x || top.second != y);
    e.push_back(b);
}
void dfs(int k)
{
    disc[k] = low[k] = ++temp;
    for(auto v : a[k]) {
        if(!disc[v]) {
            st.push(make_pair(k, v));
            dfs(v);
            low[k] = min(low[k], low[v]);
            if(low[v] >= disc[k])
                found(k, v);
        }
        else
            low[k] = min(low[k], disc[v]);
    }
}
int main()
{
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
        dfs(1);
        fout << e.size() << "\n";
        for(int i = 0; i < e.size(); ++i) {
            sort(e[i].begin(), e[i].end());
            e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
            for(int j = 0; j < e[i].size(); ++j) fout << e[i][j] << " ";
            fout << "\n";
        }
    return 0;
}