Cod sursa(job #2924630)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 6 octombrie 2022 19:49:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <fstream>
#include<vector>
#include<stack>
#include<cstring>
#include<unordered_set>
using namespace std;
#define MAXN 100005
#define NIL -1
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[MAXN];
vector<vector<int> >bic;
int df[MAXN], edge[MAXN];
stack<pair<int, int> > s;
void constructBick(int a, int b){
    pair<int, int> goldStandard=make_pair(a, b), p;///standardul de aur
    pair<int, int> silver={b, a};
    vector<int> currComp;
    do{
      p=s.top();///golim stiva, facem biconexa de pana acum
      currComp.push_back(p.first);
      currComp.push_back(p.second);
      s.pop();
    }while(p!=goldStandard&&s.size()>0);
    bic.push_back(currComp);
}
void dfs(int i, int prev, int depth){///stiva dfs e inerenta in recursie
    df[i]=edge[i]=depth;
    for(int j=0; j<g[i].size(); j++){
        if(g[i][j]!=prev){ ///daca nu se intoarce
            if(df[g[i][j]]==NIL){//daca e nevizitat
                s.push(make_pair(i, g[i][j]));//muchia merge pe stiva
                dfs(g[i][j], i, depth+1);
                edge[i]=min(edge[i], edge[g[i][j]]);
                if(edge[g[i][j]]>=df[i])
                    constructBick(i, g[i][j]);
            }
            else{///am muchie inapoi in arborele DFS
                edge[i]=min(edge[i], df[g[i][j]]);//o pun
            }
        }
    }
}
void filterVector(vector<int> a){
    unordered_set<int> s; int n=a.size();
    for(int i=0; i<n; i++){
        if(s.find(a[i])==s.end()){
            fout<<a[i]<<" ";
        }
        s.insert(a[i]);
    }
    fout<<"\n";
}
int main()
{
    int n, e; fin>>n>>e;
    for(int i=0; i<e; i++){
        int x, y; fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    memset(df, NIL, sizeof(df));///cifram diferit nevizitarea de adancimea nula
    dfs(1, 0, 0);
    fout<<bic.size()<<"\n";
    for(int i=0; i<bic.size(); i++){
        filterVector(bic[i]);
    }
    return 0;
}