Cod sursa(job #3220967)

Utilizator diana_dd03Dorneanu Diana diana_dd03 Data 5 aprilie 2024 16:16:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

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

int N, M, t;
vector<int>ad[100005];
int disc[100005];
int low[100005];
vector<int> S;
vector<vector<int>> sol;

void Dfs( int nod, int parent ) {
    disc[nod]=low[nod]=++t;
    S.push_back(nod);

    int w;
    for(int i=0;i<ad[nod].size();++i){
        w=ad[nod][i];

        if(w==parent) continue;

        if(disc[w]>0 )
            low[nod]=min(low[nod], disc[w]);
        else{
            Dfs(w, nod);
            low[nod]=min(low[nod], low[w]);

            if(low[w]>=disc[nod]){
                vector <int> tmp;

                while(S.back()!=w){
                    tmp.push_back(S.back());
                    S.pop_back();
                 }
                 tmp.push_back(S.back());
                 S.pop_back();

                 tmp.push_back(nod);
                 sol.push_back(tmp);
          }
       }
    }

}


int main(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int a, b;
        fin>>a>>b;
        ad[a].push_back(b);
        ad[b].push_back(a);
    }
    for(int i=1;i<=N;++i)
      if(disc[i]==0)
        Dfs(i, 0);

    fout<<sol.size()<<'\n';
    for(int i=0;i<sol.size();++i){
       for(int j=0;j<sol[i].size();++j)
           fout<<sol[i][j]<< ' ';
        fout << '\n';
    }
    return 0;
}