Cod sursa(job #2179965)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 20 martie 2018 15:53:06
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.02 kb
#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;

struct nod{
    //int index;
    int level;
    int min_level; /// dfn
    int min_father_index;
};

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

vector<int> veciniCopy[N];
vector<int> vecini[N];
int viz[N];
nod v[N];
int n,m;

void input(){
    in>>n>>m;
    for(int i=0; i<m; ++i){
        int a,b;
        in>>a>>b;
        vecini[a].push_back(b);
        vecini[b].push_back(a);

        veciniCopy[a].push_back(b);
        veciniCopy[b].push_back(a);
    }
}

void output(){
    vector<int> components[N];
    for(int i=1; i<=n; ++i)
        components[v[i].min_father_index].push_back(i);

    /// Count Subgraphs
    int count_subgraphs = 0;
    for(auto &c : components)
        if(c.size() > 1)
            ++count_subgraphs;

    for(int i=1; i<=n; ++i)
        for(auto &vecin : veciniCopy[i])
            if(i <= vecin)
                if(v[i].min_father_index != v[vecin].min_father_index)
                    ++count_subgraphs;

    out<<count_subgraphs<<"\n";

    /// Print Subgraphs
    for(auto &c : components){ /// Print subgraphs of min. size 2
        if(c.size() > 1) {
            for(auto &node : c) {
                out<<node<<" ";
            }
            out<<"\n";
        }
    }

    for(int i=1; i<=n; ++i) /// Print critical edge subgraphs
        for(auto &vecin : veciniCopy[i])
            if(i <= vecin) /// Don't print duplicates!
                if(v[i].min_father_index != v[vecin].min_father_index)
                    out<<i<<" "<<vecin<<"\n";
}

void afis_vecini(){
    for(int i=1; i<=n; ++i){
        cout<<i<<": ";
        for(auto &x : vecini[i])
            cout<<x<<" ";
        cout<<"\n";
    }cout<<"\n";
}

void afis_noduri(){
    for(int i=1; i<=n; ++i){
        cout<<i<<": level = "<<v[i].level<<", min_level = "<<v[i].min_level<<", min_father_index = "<<v[i].min_father_index<<"\n";
    }
}

void find_min_level(int index, int level){
    if(viz[index] == 1)
        return;

    ///cout<<"Visiting "<<index<<"\n";

    v[index].level = level;
    v[index].min_level = level;
    v[index].min_father_index = index;
    viz[index] = 1;

    for(auto vecinIndex : vecini[index]){
        ///cout<<"  Vecin "<<vecinIndex<<"\n";
        vecini[index].erase( remove(vecini[index].begin(), vecini[index].end(), vecinIndex), vecini[index].end());
        vecini[vecinIndex].erase( remove(vecini[vecinIndex].begin(), vecini[vecinIndex].end(), index), vecini[vecinIndex].end());
        find_min_level(vecinIndex, level+1);
        if(v[vecinIndex].min_level < v[index].min_level){
            v[index].min_level = v[vecinIndex].min_level;
            v[index].min_father_index = v[vecinIndex].min_father_index;
        }
    }
    ///cout<<"-- up --\n";
}

int main()
{
    input();
    //afis_vecini();
    find_min_level(1, 1);
    //afis_noduri();
    output();

    return 0;
}