Cod sursa(job #2525926)

Utilizator mirceatlxhaha haha mirceatlx Data 18 ianuarie 2020 00:42:43
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 10005
using namespace std;

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

vector <int> G[NMAX], ans[NMAX];
vector <int> dfsDiscover, dfsLow, articulationVertex, dfsParent, visited;
stack <int> st;
int timex, dfsRoot, rootChildren, N, M, K;

void articulationPoint(int node)
{
    int nodex;
    ++timex;
    st.push(node);
    dfsDiscover[node] = dfsLow[node] = timex;
    for(int j = 0; j < G[node].size(); j++){
        nodex = G[node][j];
        if(!dfsDiscover[nodex]){
            dfsParent[nodex] = node;
            if(node == dfsRoot){
                rootChildren++;
            }
            articulationPoint(nodex);
            dfsLow[nodex] = min(dfsLow[node],dfsLow[nodex]);
            if(dfsLow[nodex] >= dfsDiscover[node]){
                articulationVertex[node] = true;
                ++K;
                while(st.top() != nodex){
                    ans[K].push_back(st.top());
                    st.pop();
                }
                ans[K].push_back(node);
                ans[K].push_back(nodex);
                st.pop();
            }
        }
        else{
            if(nodex != dfsParent[node]){
                dfsLow[node] = min(dfsLow[node],dfsDiscover[nodex]);
            }
        }
    }
}

int main()
{
    int x, y;
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfsParent.assign(N + 1,-1);
    articulationVertex.assign(N + 1,0);
    dfsLow.assign(N + 1,0);
    dfsDiscover.assign(N + 1,0);
    for(int i = 1; i <= N; i++){
        if(!dfsDiscover[i]){
            dfsRoot = i;
            rootChildren = 0;
            articulationPoint(i);
            articulationVertex[dfsRoot] = (rootChildren > 1);
        }
    }
    fout << K << "\n";
    for(int i = 1; i <= K; i++){
        for(int j = 0; j < ans[i].size(); j++){
            fout << ans[i][j] << " ";
        }
        fout << "\n";
    }
    return 0;
}