Cod sursa(job #2250582)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 30 septembrie 2018 14:52:27
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int MaxN=100005;
vector <int> G[MaxN];
int Niv[MaxN],Low[MaxN],Viz[MaxN],N,M;
vector <vector <int> > Sol;
stack <int > St;

void Add(int Nod,int Fiu){
    vector <int> Ans;
    while(St.top()!=Fiu){
        Ans.push_back(St.top());
        St.pop();
    }
    St.pop();
    Ans.push_back(Fiu);
    Ans.push_back(Nod);
    Sol.push_back(Ans);
}

void DFS(int Nod,int K){
    Viz[Nod]=1;
    for(int i : G[Nod]){
        if(i==K)
            continue;
        if(Viz[i]==1)
            Low[Nod]=min(Low[Nod],Niv[i]);
        else{
            St.push(i);
            Niv[i]=Niv[Nod]+1;
            DFS(i,Nod);
            Low[Nod]=min(Low[Nod],Low[i]);
            if(Low[i]>=Niv[Nod])
                Add(Nod,i);
        }
    }
}

void Read(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int X,Y;
        fin>>X>>Y;
        G[X].push_back(Y);
        G[Y].push_back(X);
    }
}

int main(){
    Read();
    for(int i=1;i<=N;i++)
        Low[i]=100;
    for(int i=1;i<=N;i++)
        if(Viz[i]==0)
            DFS(i,0);
    fout<<Sol.size()<<'\n';
    for(int j=0;j<Sol.size();j++){
        for(int i : Sol[j])
            fout<<i<<" ";
        fout<<'\n';
    }
    return 0;
}