Cod sursa(job #1958559)

Utilizator Train1Train1 Train1 Data 8 aprilie 2017 14:54:15
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMax 100001
#define MMax 200001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int low[NMax], dfn[NMax], n, m, x, y, ordin, fii, nr, RAD;
bool viz[NMax];
vector <int> comp[NMax];
vector <int> v[NMax];
stack <pair <int, int> > st;
void getComp(int ArtPoint) {
    pair <int, int> edge = st.top();
    while(edge.first != ArtPoint) {
        st.pop();
        comp[nr].push_back(edge.second);
        edge = st.top();
    }
    st.pop();
    comp[nr].push_back(edge.second);

    comp[nr].push_back(ArtPoint);
}
void dfs(int nod, int Tnod) {
    ordin++;
    dfn[nod] = ordin;
    low[nod] = ordin;
    viz[nod] = true;
    st.push(make_pair(Tnod, nod));
    for(int i = 0; i < v[nod].size(); i++) {
        int fiu = v[nod][i];
        if(fiu == Tnod)
            continue;
        if(viz[fiu]) {
            low[nod] = min(low[nod], low[fiu]);//
            continue;
        }
        // if(nod == RAD) fii++;
        dfs(fiu, nod);
        low[nod] = min(low[nod], low[fiu]);
        if(low[fiu] >= dfn[nod]) {
            getComp(nod);
            nr++;
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; i++) {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    RAD = 1;
    dfs(1, 0);
    fout<<nr;
    fout<<'\n';
    for(int i = 0; i < nr; i++) {
        for(int j = 0 ; j < comp[i].size(); j++) {
            fout<<comp[i][j]<<' ';
        }
        fout<<'\n';
    }
    /*
    for(int i = 1; i <= n; i++) {
        fout<<dfn[i]<<" ";
    }
    fout<<'\n';
    for(int i = 1; i <= n; i++) {
        fout<<low[i]<<" ";
    }
    */
    fin.close();
    fout.close();
    return 0;
}