Cod sursa(job #2668220)

Utilizator CryshanaGanea Carina Cryshana Data 4 noiembrie 2020 17:36:49
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define MAX 100001
using namespace std;

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

int N, M;
bool viz[MAX];
int tata[MAX];
queue<pair<int,int>> q;
queue<pair<int,int>> bck;
vector<int> graf[MAX];
vector<vector<int>> conex;

void dfs ( int x ){
    viz[x] = true;
    for( auto y : graf[x])
        if( !viz[y]){
            q.push(make_pair(x,y));
            tata[y] = x;
            dfs(y);
        }
        else if (y != tata[x]){
            bck.push(make_pair(x,y));
        }
}

int main(){

    in >> N >> M;

    for( int i = 0; i < M ; i++){
        int x, y;
        in >> x >> y;

        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    dfs(1);

    while( !q.empty() ){
        vector<int> comp;
        if( !bck.empty() && bck.front().second == q.front().first){

            while( q.front().second != bck.front().first && !q.empty()){
                comp.push_back(q.front().first);
                //out << "(" << q.front().first << "; " << q.front().second << ") ";
                q.pop();
            }
            //out << "(" << q.front().first << "; " << q.front().second << ") ";
            bck.pop();
            bck.pop();
            //out << bck.front().first << "," << bck.front().second;
        }

        //out << "(" << q.front().first << "; " << q.front().second << ") ";
        comp.push_back(q.front().first);
        comp.push_back(q.front().second);
        q.pop();

        conex.push_back(comp);
    }

    out << conex.size() << "\n";

    for( auto v : conex){
        for ( auto x : v)
            out << x << " ";
        out << "\n";
    }
    return 0;
}