Cod sursa(job #2199296)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 27 aprilie 2018 10:36:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

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

const int kMax = 100001;
int n, m, d[kMax], low[kMax], nrb = 0, times = 0;
vector<int> v[kMax], G[kMax];
stack< pair<int, int> >stk;
pair<int, int> pa;

void DFSs(int k, int &times) {
    d[k] = ++times;
    low[k] = d[k];

    for (int i = 0; i < G[k].size(); i++) {

        if (d[G[k][i]] == 0) {

            stk.push(make_pair(k, G[k][i]));
            DFSs(G[k][i], times);
            low[k] = min(low[k], low[G[k][i]]);
            
            if (low[G[k][i]] >= d[k]) {
                nrb++;
                pa = stk.top();
                while (pa.first != k) {
                    v[nrb].push_back(pa.second);
                    stk.pop();
                    pa = stk.top();
                }
                stk.pop();
                v[nrb].push_back(pa.first);
                v[nrb].push_back(pa.second);
                sort(v[nrb].begin(), v[nrb].end());
            }
        }
        else {
            low[k] = min(low[k], d[G[k][i]]);
        }
        
    }
    
}

int main() {
    fin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
            DFSs(i, times);
    
    fout << nrb << '\n';
    for (int i = 1; i <= nrb; i++){
        for (int j = 0; j < v[i].size(); j++)
            fout << v[i][j] << " ";
        fout << '\n';
    }
    
    fin.close();
    fout.close();
    return 0;
}