Cod sursa(job #1020688)

Utilizator sziliMandici Szilard szili Data 2 noiembrie 2013 14:49:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>

using namespace std;

typedef struct nnode{
    int low;
    int distance;
} NODE;

typedef struct edge{
    int a;
    int b;
} EDGE;

vector<int> adjacencyList[100002];
int n,m;

NODE nodes[100002];
stack<EDGE> edgeStack;
int solutionNr;
vector<int> solution[100002];

int currentDistance = 1;

int minn(int a, int b){

    if (a<b){
        return a;
    } else return b;
}

void dfs(int node, int from){
    nodes[node].distance = currentDistance;
    nodes[node].low = currentDistance;

    currentDistance++;
    int ss = adjacencyList[node].size();

    for (int i=0; i<ss; i++){
        if (!nodes[adjacencyList[node][i]].distance){
            EDGE e;
            e.a = node;
            e.b = adjacencyList[node][i];

            edgeStack.push(e);

            dfs(adjacencyList[node][i], node);

            if (nodes[adjacencyList[node][i]].low >= nodes[node].distance){

                while (edgeStack.top().a != node){
                    solution[solutionNr].push_back(edgeStack.top().b);
                    edgeStack.pop();
                }

                solution[solutionNr].push_back(edgeStack.top().a);
                solution[solutionNr].push_back(edgeStack.top().b);
                edgeStack.pop();

                solutionNr++;
            }

            nodes[node].low = minn(nodes[adjacencyList[node][i]].low, nodes[node].low);

        } else if (adjacencyList[node][i] != from) {
            nodes[node].low = minn(nodes[adjacencyList[node][i]].low, nodes[node].low);
        }
    }

}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int nod1, nod2;
    for (int i=0; i<m; i++){
        scanf("%d %d", &nod1, &nod2);
        adjacencyList[nod1].push_back(nod2);
        adjacencyList[nod2].push_back(nod1);
    }


    for (int i=1; i<=n; i++){
        if (!nodes[i].distance){
            dfs(i, -1);
        }
    }


    printf("%d\n", solutionNr);

    for (int i=0; i<solutionNr; i++){

        for (int j=0; j<solution[i].size(); j++){
            printf("%d ", solution[i][j]);
        }
        printf("\n");
    }


    return 0;
}