Cod sursa(job #2173916)

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

struct muchie{

    int x,y;
}vect[2*N];
vector <int> V[N];
vector <int> Muchii[N];
vector <int> sol[N];
vector <int> mult[N];
stack  <int> s;
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 mch = Muchii[poz][i];
        int ad = V[poz][i];

        if(niv[ad]==0){

            s.push(mch);
            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);
        Muchii[x].push_back(i);
        Muchii[y].push_back(i);
        vect[i].x = x;
        vect[i].y = y;

    }
    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;
}