Cod sursa(job #2264872)

Utilizator BlkAlexAlex Negru BlkAlex Data 20 octombrie 2018 12:19:51
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
#define MAX 100100

using namespace std;

ifstream f("date.in");
ofstream g("date.out");

vector <int> v[MAX];
stack < pair <int, int> > st;
vector <int> sol;

int n, m;
int nr;

int lvl[MAX], low[MAX];

void comp_bic(int x, int y){
    int tx, ty; //topul stivei
    do{
        tx=st.top().first;
        ty=st.top().second;
        st.pop();
        sol.push_back(tx);
        sol.push_back(ty);
    }while (tx != x || ty != y);
    int i;
    sort(sol.begin(),sol.end());
    sol.erase(unique(sol.begin(),sol.end()),sol.end());//scoate dublurile
    for(i=0; i<sol.size(); i++){
        g<<sol[i]<<" ";
    }
    g<<"\n";
    sol.clear();
}

void dfs (int nod, int t){

    lvl[nod]=lvl[t]+1;
    low[nod]=lvl[nod];
    for (auto &w:v[nod]){
        if(w!=t){
            if(!lvl[w]){
                st.push(make_pair(nod, w));
                // sau st.push({nod, w});
                dfs(w, nod);
                if(nod==1) nr++;
                low[nod]=min(low[nod], low[w]);
                if(low[w]>=lvl[nod]){
                    comp_bic(nod, w);
                    }
            } else {
                low[nod]=min(low[nod], lvl[w]);
            }
        }
    }
}

int main()
{
    int i, x, y;
    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    //dupa aia cu solutia asta facem ce vrem, o afisam o... (*avem dubluri)
    g<<"\n\n\n\n";
    return 0;
}