Cod sursa(job #1412495)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 1 aprilie 2015 12:24:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <set>
#include <stack>
#define per pair<int,int>
#define mper make_pair
#define x first
#define y second
#define nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
int low[nmax],cbc;
vector <int> v[nmax];//Liste de adiacenta
bitset <nmax> uz;
set <int> r[nmax];//Solutiile biconexe
set <int> :: iterator it;
stack <per> s;
per p;

//Fac dfs pentru un nod retinand nivelul si tatal nodului
void dfs(int nod,int niv,int tata)
{
    uz[nod]=1;
    low[nod]=niv;
    int i,fiu;
    for (i=0;i<v[nod].size();i++) {
        fiu=v[nod][i];
        //Iterez pentru fiecare fiu
        if (fiu==tata)
            continue;
        //Am grija sa nu ma intorc in tata
        if (uz[fiu]==0) {
            //Daca nu s-a mai ajuns in fiu
            s.push(mper(nod,fiu));
            dfs(fiu,niv+1,nod);
            low[nod]=min(low[nod],low[fiu]);
            //Actualizez vectorul low
            if (low[fiu]>=niv) {
                //Construiesc componenta biconexa noua
                cbc++;
                do {
                    p=s.top();
                    s.pop();
                    r[cbc].insert(p.x);
                    r[cbc].insert(p.y);
                } while ((nod!=p.x||fiu!=p.y));
            }
        }
        else
            low[nod]=min(low[nod],low[fiu]);

    }

}
int main()
{
    int i,j,a,b;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        //Creez graful
    }
    for (i=1;i<=n;i++)
        if (!uz[i])
            dfs(i,1,0);
        //Parcurg componentele conexe
    g<<cbc<<'\n';
    for (i=1;i<=cbc;i++) {
        for (it=r[i].begin();it!=r[i].end();it++)
            g<<*it<<' ';
        g<<'\n';
    }
    return 0;
}