Cod sursa(job #1954011)

Utilizator ticozaurStratila Andrei ticozaur Data 5 aprilie 2017 10:02:33
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> v[NMAX];
vector<int> sol[NMAX];
vector<bool> viz;
int m,n,x,y,vf,nr,niv[NMAX],up[NMAX],st[NMAX];
void dfs(int nod,int tata)
{
    viz[nod]=true;
    niv[nod]=niv[tata]+1;
    up[nod]=niv[nod];
    st[++vf]=nod;
    for(int i=0; i<v[nod].size(); i++){
        if(viz[v[nod][i]]!=false){
            if(viz[v[nod][i]]!=tata)
                up[nod]=min(up[nod],niv[v[nod][i]]);
        }
        else{
            dfs(v[nod][i],nod);
            up[nod]=min(up[nod],up[v[nod][i]]);
            if(up[v[nod][i]]>=niv[nod]){
                ++nr;
                while(st[vf]!=v[nod][i])
                    sol[nr].push_back(st[vf--]);
                sol[nr].push_back(nod);
                sol[nr].push_back(v[nod][i]);
                vf--;
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    viz.resize(n,false);
    for(int i=0; i<m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    fout<<nr;
    fout<<'\n';
    for(int i=1;i<=nr;i++){
        for(vector<int>::iterator j=sol[i].begin(); j!=sol[i].end(); j++){
            fout<<*j<<' ';
        }
        fout<<'\n';
    }
    return 0;
}