Cod sursa(job #2242108)

Utilizator danielsociuSociu Daniel danielsociu Data 17 septembrie 2018 19:58:39
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream cin("biconex.in");
std::ofstream cout("biconex.out");
using namespace std;
#define maxn 200030
#define min2(a,b) a<b?a:b
vector <int> adj[maxn]; //graf
int dfn[maxn],low[maxn],N,M;
vector <vector<int>> C;//componente biconexe
stack <pair<int,int>> stk; //depozitare laturi +comp biconexe

void citire(){
    int x,y;
    cin>>N>>M;
    for(;M--;){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void cache_clear(int x,int y){//adauga o comp biconexa
    vector <int> comp_bicon; //la rezultat(C)
    int tx,ty;
    do{
        tx=stk.top().first; ty=stk.top().second;
        stk.pop();
        comp_bicon.push_back(tx); comp_bicon.push_back(ty);
    }while(tx!=x||ty!=y);
    C.push_back(comp_bicon);
}

void dfs_anc(int n, int fn, int number) //fn nod anterior
{
    vector <int>::iterator it;
    low[n]=dfn[n]=number;
    for(it=adj[n].begin();it!=adj[n].end();it++){
        if(*it==fn) //daca nod ant ==not actual
            continue;
        if(!dfn[*it]){
            stk.push(make_pair(n,*it));
            dfs_anc(*it,n,number+1);
            low[n]=min2(low[*it],low[n]);
            if(dfn[n]<=low[*it])
                cache_clear(n,*it);
        }
        else
            low[n]=min2(low[*it],low[n]);
    }//dfn retine val initiale
}//low valorile minime de parcurgere

int main()
{
    citire();
    dfs_anc(1,-1,1);
    int nrsol=0;
    for(unsigned int i=0;i<C.size();i++)
        nrsol++;

    cout<<nrsol<<'\n';
    for(unsigned int i=0;i<C.size();i++){
        sort(C[i].begin(),C[i].end());
        C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
        //Linia de mai sus sterge tot de dupa poz care o returneaza unique, pana la end()
        //Unique sterge toate elementele care se repeta, mutand restul catre stanga si
        //returneaza pozitia ultimului elem+1.
        //Asa merge sa retina cate elem exact are C[i]
        //erase e din <vector> unique e din <algorithm>
        vector<int>::iterator it;
        for(it=C[i].begin();it!=C[i].end();it++)
            cout<<*it<<' ';//nu e nevoie de iterator
        cout<<'\n';//la citire pt ca nu prea modificam
    }  //ar fi fost bine si un alt unsigned int for si C[i][j];
}