Cod sursa(job #2117760)

Utilizator omegasFilip Ion omegas Data 29 ianuarie 2018 16:37:04
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
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;
int Q;

graf* v[100001];
int comp[100001];
int d[100001];
int tati[100001];
int low[100001];
int t = 1;
int c = 1;
int counter=0;
int root =1;


edge st[200001];
int len;
int sonsOfRoot;

void pop(){
    edge x;

    if(col[st[len].v1]!= Q){
        x.v1 = st[len].v1;
        x.v2 = Q;
        print.push_back(x);
        col[st[len].v1] = Q;
    }
    if(col[st[len].v2]!= Q){
        x.v1 = st[len].v2;
        x.v2 = Q;
        print.push_back(x);
        col[st[len].v2] = Q;
    }
    --len;
}

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){
    low[node] = d[node] = t;
    ++t;

            ++len,
            st[len].v1 = dad,
            st[len].v2 = node;

    comp[node] = c;
    graf *p;
    p=v[node];
    while(p!=NULL){
        if(comp[p->nod] == 0){
            DFS(p->nod, node),
            tati[p->nod] = node;
            if(node == root && sonsOfRoot < 2)
                ++sonsOfRoot;
            if(d[node] <= low[p->nod]){
                ++Q;
                ++ counter;
                while(st[len].v1!=node||st[len].v2!=p->nod){
                    pop();
                }
                pop();
            }
        }
        if(p->nod!=dad && low[node] > low[p->nod]){
            low[node] = low[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(comp[i]==0){
                root = i;
                DFS(i,0);
            }
    }
    fout << counter << 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;
}