Cod sursa(job #1739815)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 10 august 2016 12:22:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>
#define inf 1<<30
#define x first
#define y second

using namespace std;

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

stack <pair <int,int> > Stack;
vector <int> sol[100001];
vector <int> v[100001];
int idx[100001], mini[100001];
int i, a, b, j, n, m, maxi, l, k, lungime, solution;

void dfs (int nod, int parinte)
{
    int i, x;
    idx[nod] = mini[nod] = idx[parinte] + 1;
    for (i=0; i<v[nod].size(); i++)
        if (v[nod][i] != parinte)
        {
            if (!idx[v[nod][i]])
            {
                Stack.push(make_pair(nod,v[nod][i]));
                dfs(v[nod][i],nod);
                if (mini[v[nod][i]] >= idx[nod])
                {
                    a = 0;
                    b = 0;
                    solution++;
                    do
                    {
                        a = Stack.top().x;
                        b = Stack.top().y;
                        Stack.pop();
                        sol[solution].push_back(b);
                    } while (a != nod && b != v[nod][i]);
                    sol[solution].push_back(nod);
                }
            }
            mini[nod] = min(mini[nod],mini[v[nod][i]]);
        }
}

int main ()
{
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    fout << solution << '\n';
    for (i=1; i<=solution; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    return 0;
}