Cod sursa(job #2118735)

Utilizator omegasFilip Ion omegas Data 30 ianuarie 2018 22:01:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

struct graf{
int nod;
int dist;
graf* next;
};

struct edge{
int v1,v2;
};

vector <int> col(100001);
vector < edge > print;
vector <edge> cache[100001];
int Q;

graf* v[100001];
bool vis[100001];
int d[100001];
int low[100001];
int c = 1;


stack <edge> stk;
int len;

void load(){
    edge y,x;
    y = stk.top();

    if(col[y.v1]!= Q){
        x.v1 = y.v1;
        x.v2 = Q;
        print.push_back(x);
        col[y.v1] = Q;
    }
    if(col[y.v2]!= Q){
        x.v1 = y.v2;
        x.v2 = Q;
        print.push_back(x);
        col[y.v2] = Q;
    }
    stk.pop();
}



void add(int a, int b)
{
    graf* q = new graf;
    q->nod  = b;
    q->next = v[a];
    v[a] = q;
}


void DFS(int node, int dad, int level){
    low[node] = d[node] = level;

    edge x;
    x.v1 = dad;
    x.v2 = node;
    if(dad)
    stk.push(x);

    vis[node] = 1;

    graf *p = v[node];
    while(p!=NULL){
        if(vis[p->nod] == 0){
            DFS(p->nod, node, level + 1);

            if(d[node] <= low[p->nod]){
                ++Q;
                while(stk.top().v1!=node||stk.top().v2!=p->nod){
                    load();
                }
                load();
            }
            if(low[node] > low[p->nod]){
            low[node] = low[p->nod];
            }
        }
        if(p->nod!=dad && low[node] > d[p->nod]){
            low[node] = d[p->nod];
        }
        p = p->next;
    }
}




int main()
{
    int i,x,y;
    int n,m;
    fin >> n >> m;
    for(i=1;i<=m;++i){
        fin >> x >> y;
        add(x,y);
        add(y,x);
    }

    for(i=1;i<=n;++i)
        if(vis[i]==0)
            DFS(i,0,1);

    fout  << Q << endl;
    for (int i = 0; i < print.size(); i++) {
            if(i >= 1 && print[i].v2 != print[i-1].v2)
            fout << "\n";
            fout << print[i].v1 << " ";
        }



    return 0;
}