Cod sursa(job #1816531)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 26 noiembrie 2016 16:28:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

vector<int> v[100010];
vector<vector<int> > sol;
vector<pair<int,int> > q;
int niv[100010],nivmin[100010];
bool vaz[100010];
int n,m;

void comp_biconexa(int x,int y)
{
    int a,b;
    vector<int> aux;
    do
    {
        a=q.back().first,b=q.back().second;
        q.pop_back();
        aux.push_back(b);
    }while(x!=a or y!=b);
    aux.push_back(a);
    sol.push_back(aux);
}

void dfs(int node,int level){
    vaz[node]=true;
    niv[node]=nivmin[node]=level;
    for (auto i:v[node])
        if(!vaz[i]){
            q.push_back({node,i});
            dfs(i,1+level);
            nivmin[node]=min(nivmin[node],nivmin[i]);
            if(nivmin[i]>=niv[node]) comp_biconexa(node,i);}
        else nivmin[node]=min(nivmin[node],niv[i]);
}

int main()
{
    int x,y;
    f>>n>>m;
    for (int i=0;i<m;++i)
        f>>x>>y,v[x].push_back(y),v[y].push_back(x);
    for(int i=0;i<n;++i)
        if(!vaz[i]) dfs(i,0);
    t<<sol.size()<<'\n';
    for (auto i:sol){
        for (auto j:i)
        t<<j<<" ";
    t<<'\n';}
    return 0;
}