Cod sursa(job #2173920)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 16 martie 2018 09:41:15
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 100005;
ifstream f("biconex.in");
ofstream g("biconex.out");

vector <int> V[N];
vector <int> sol[N];
vector <int> mult[N];
int low[N],niv[N];
bool isParc[N];
int n,m,nr,cif;

void dfs(int poz,int lst){

    int sz = V[poz].size();
    cif++;
    low[poz] = cif;
    niv[poz] = cif;

    for(int i = 0; i< sz; i++){

        int ad = V[poz][i];

        if(niv[ad]==0){

            dfs(ad,poz);
            low[poz] = min(low[poz],niv[ad]);
            low[poz] = min(low[poz],low[ad]);


            if(niv[poz]<low[ad]){

                nr++;
                sol[nr].push_back(poz);
                sol[nr].push_back(ad);
            }

        }
        else if(niv[ad]<niv[poz]&&ad!=lst){
            low[poz] = min(low[poz],low[ad]);
            low[ad]  = low[poz];
        }
    }
    mult[low[poz]].push_back(poz);
}


int main(){

    f>>n>>m;

    for(int i =1; i<= m; i++){
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    dfs(1,0);
    for(int i =1; i<= n; i++){
        //g<<i<<" "<<niv[i]<<" "<<low[i]<<"\n";
    }
    for(int i = 1; i<= n; i++){
        int sz = mult[i].size();
        if(sz>1){
            nr++;
            for(int j =0; j< sz; j++){
                sol[nr].push_back(mult[i][j]);
                //g<<mult[i][j]<<" ";
            }
            //g<<"\n";
        }
    }

    g<<nr<<"\n";
    for(int i =1; i<= nr; i++){
        int sz = sol[i].size();
        sort(sol[i].begin(),sol[i].end());
        for(int j =0; j< sz; j++){
            g<<sol[i][j]<<" ";
        }
        g<<"\n";
    }
    f.close();
    g.close();
    return 0;
}