Cod sursa(job #1003951)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 1 octombrie 2013 20:00:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

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

struct node {
    bool vizitat;
    int mini;
    int grad;
    vector<int> vecini;
};

struct cuplu {
    int a;
    int b;
};

int n, m, i, ii, a, b, s1, s2;
node nodes[100001];
cuplu muchie;
stack<cuplu> stiva;
vector<int> sol;
vector<vector<int> > solutie;

void dfs(int x) {
    int j;
    int l = nodes[x].vecini.size();
    for(j = 0; j < l; j++) {
        int vecin = nodes[x].vecini[j];
        if(nodes[vecin].vizitat == false) {
            muchie.a = x;
            muchie.b = vecin;
            stiva.push(muchie);
            nodes[vecin].vizitat = true;
            nodes[vecin].grad = nodes[vecin].mini = nodes[x].grad + 1;
            dfs(vecin);
            nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
            if(nodes[vecin].mini >= nodes[x].grad) {
                do {
                    muchie = stiva.top();
                    stiva.pop();
                    sol.push_back(muchie.b);
                }while(muchie.a != x);
                sol.push_back(muchie.a);
                solutie.push_back(sol);
                sol.clear();
            }
        }
        else {
            if(nodes[vecin].grad != nodes[x].grad - 1) {
                nodes[x].mini = min(nodes[x].mini, nodes[vecin].grad);
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for(i = 0; i < m; i++) {
        fin >> a >> b;
        nodes[a].vecini.push_back(b);
        nodes[b].vecini.push_back(a);
    }
    nodes[1].grad = 1;
    nodes[1].mini = 1;
    nodes[1].vizitat = true;
    dfs(1);
    s1 = solutie.size();
    fout << s1 << '\n';
    for(i = 0; i < s1; i++) {
        sol = solutie[i];
        s2 = sol.size();
        for(ii = s2 - 1; ii >= 0; ii--) {
            fout << sol[ii] << ' ';
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}