Cod sursa(job #2682542)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 8 decembrie 2020 21:01:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
using namespace std;

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

const int N = 100000;

vector <int> G[N + 1];
vector <int> comp[N + 1];
vector <int> stiva;

int low[N + 1], num[N + 1];
bool visited[N + 1];

int biconexGraphs;
int rootChildren;
int ord;

void biconex(int node, int parent){
    stiva.push_back(node);
    visited[node] = true;
    low[node] = num[node] = ++ord;

    for(int i = 0; i < (int)G[node].size(); i++){
        int next = G[node][i];
        if(!visited[next]){
            if(node == 1)
                rootChildren++;
            biconex(next, node);

            if(num[node] <= low[next]){
                biconexGraphs++;

                while(stiva.back() != next){
                    comp[biconexGraphs].push_back(stiva.back());
                    stiva.pop_back();
                }
                comp[biconexGraphs].push_back(next);
                comp[biconexGraphs].push_back(node);
                stiva.pop_back();
            }
            low[node] = min(low[node], low[next]);
        }
        else if(next != parent)
            low[node] = min(low[node], num[next]);
    }
}

int main()
{
    int n, m, i, x, y;
    fin >> n >> m;
    for(i = 0; i < m; i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    biconex(1, -1);
    fout << biconexGraphs << "\n";
    for(i = 1; i <= biconexGraphs; i++){
        for(int j = 0; j < (int)comp[i].size(); j++)
            fout << comp[i][j] << " ";
        fout << "\n";
    }
    return 0;
}