Cod sursa(job #1486359)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 14 septembrie 2015 18:49:16
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,nr_rez;
vector<int> v[100010];
vector<vector<int> > rez;
int nr_dfs[100010],after[100010];

struct elem {
    int x,y;
};
stack<elem> s;

void dfs(int,int,int);
void retine_componenta(int,int);

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        int x,y;
        f>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0,1);
    g<<nr_rez<<'\n';
    for (unsigned int i=0;i<rez.size();++i) {
        for (unsigned int k=0;k<rez[i].size();++k) {
            g<<rez[i][k]<<' ';
        }
        g<<'\n';
    }
    f.close();g.close();
    return 0;
}

void dfs(int nod,int dad,int nr) {
    nr_dfs[nod]=after[nod]=nr;
    for (unsigned int k=0;k<v[nod].size();++k) {
        int fiu=v[nod][k];
        if (nr_dfs[fiu]==0) {
            elem A;
            A.x=nod;A.y=fiu;
            s.push(A);
            dfs(fiu,nod,nr+1);
            after[nod]=min(after[nod],after[fiu]);
            if (after[fiu]>=nr_dfs[nod]) {
                retine_componenta(nod,fiu);
            }
        }
        else if (fiu!=dad && after[fiu]<after[nod]) {
            after[nod]=after[fiu];
        }
    }
}

void retine_componenta(int x,int y) {
    vector<int> aux;
    elem A;
    do {
        A=s.top();
        s.pop();
        aux.pb(A.x);aux.pb(A.y);
    }
    while (A.x!=x || A.y!=y);
    sort(aux.begin(),aux.end());
    aux.erase(unique(aux.begin(),aux.end()),aux.end());
    rez.pb(aux);
    ++nr_rez;
}