Cod sursa(job #1420757)

Utilizator GodstormBotarleanu Robert Godstorm Data 18 aprilie 2015 22:02:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <sstream>

#define MAXN 100001

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define min(a,b) ((a) < (b))?(a):(b)
typedef pair<int,int> tupl;

int n, m;
int index[MAXN], lowlink[MAXN];
vector<int> adj[MAXN];
vector<bool> onStack[MAXN];
stack<tupl> S;
int vtime;
int solNr = 0;

stringstream stackout;

void printStack(int v, int n) {
    tupl comp = S.top();
    S.pop();
    if(comp.first == v && comp.second == n) return;
    printStack(v,n);
    stackout << comp.second << " ";
}

void tarjan(int const v, int const p) {
    ++vtime;
    index[v] = lowlink[v] = vtime;
    for(auto& n: adj[v]) {
        //aceeasi muchie pe care s-a ajuns la nodul v, se ignora
        if(n == p) continue;
        //nodul descendent nu e vizitat
        if(!index[n]) {
            //pus pe stiva si continuata recursiunea
            S.push(tupl(v,n));
            tarjan(n,v);
            //am vizitat toti descendentii
            lowlink[v] = min(lowlink[v], lowlink[n]);
            if(lowlink[n] >= index[v]) {
                stackout << v  <<" " << n << " ";
                printStack(v,n);
                stackout << endl;
                ++solNr;
            }
        } else {
            lowlink[v] = min(lowlink[v], lowlink[n]);
        }
    }
}

inline void read() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
       int x,y;
       fin >> x >> y;
       adj[x].push_back(y); adj[y].push_back(x);
    }
    fin.close();
}

int main() {
    read();
    tarjan(1, 0);
    fout << solNr << endl << stackout.str() << endl;
    fout.close();
    return 0;
}