Cod sursa(job #966091)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 25 iunie 2013 12:44:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

#define N 100005
#define aa first
#define bb second

using namespace std;

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

int n, m;
typedef pair <int, int> muchie;
vector <int> a[N], dfn(N, -1), low(N, -1);
vector < vector<int> > sol;
stack <muchie> st;

void Citire()
{
    while(m--)
    {
        int x, y;
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}

void Componenta_biconexa(int n, int x)
{
    vector <int> bx;
    int tx, ty;
    do
    {
        tx = st.top().aa, ty = st.top().bb;
        bx.push_back(tx); bx.push_back(ty);
        st.pop();
    }
    while(tx != n || ty != x);
    sol.push_back(bx);
}

void Dfs(const int n, const int t, int num)
{
    dfn[n] = low[n] = num;
    for(int i=0; i<a[n].size(); i++)
    {
        int x = a[n][i];
        if(x == t) continue;
        if(dfn[x] == -1)
        {
            st.push(muchie(n, x));
            Dfs(x, n, num+1);
            low[n] = min(low[n], low[x]);
            if(low[x] >= dfn[n]) Componenta_biconexa(n, x);
        }
        else if(x != t) low[n] = min(low[n], dfn[x]);
    }
}

bool cmp(const int &a, const int &b) {return a < b;}

void Write()
{
    fout<<sol.size()<<'\n';
    for(int i=0; i<sol.size(); i++)
    {
        sort(sol[i].begin(), sol[i].end(), cmp);
        fout<<sol[i][0]<<' ';
        for(int j=1; j<sol[i].size(); j++)
        if(sol[i][j] != sol[i][j-1]) fout<<sol[i][j]<<' ';
        fout<<'\n';
    }
}

int main()
{
    fin>>n>>m;
    Citire();
    Dfs(1, 0, 0);
    Write();

    return 0;
}