Cod sursa(job #952481)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 16:01:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>
#define maxn 100010
#include <fstream>
#include <stack>
 
using namespace std;
 
ifstream f("biconex.in");
ofstream g("biconex.out");
 
vector <int> A[maxn],sol[maxn];
stack <int> st;
int viz[maxn],nivel[maxn],c;
 
void solutie (int a, int b)
{
    while(st.top()!=b)
    {
        sol[c].push_back(st.top());
        st.pop();
    }
    sol[c].push_back(b);
    sol[c].push_back(a);
    c++;
    st.pop();
}
 
void df(int a, int b)
{
    viz[a] = viz[b]+1;
    nivel[a] = viz[a];
    for (int i=0;i<A[a].size();i++)
    {
        int q=A[a][i];
        if (!viz[q])
        {
            st.push(q);
            df(q,a);
            nivel[a] = min(nivel[a],nivel[q]);
            if (nivel[q]>=viz[a])
                solutie(a,q);
            else {}
        }
        else
            if (q!=b)
                nivel[a] = min(nivel[a],nivel[q]);
    }
}
 
int main()
{
    int i,a,b,n,m,j;
    f >> n >> m;
    for (i=0;i<m;i++)
    {
        f >> a >> b;
        A[a].push_back(b);
        A[b].push_back(a);
    }
    st.push(1);
    df(1,0);
    g << c << "\n";
    for (i=0;i<c;i++)
    {
        for (j=sol[i].size()-1;j>=0;j--)
            g << sol[i][j] << " ";
        g << "\n";
    }
    return 0;
}