Cod sursa(job #1698144)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 3 mai 2016 20:16:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#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> > st;
vector <int> sol[100005];
vector <int> v[100005];
int idx[100005],mini[100005];
int i,a,b,j,n,m,maxi,l,k,lungime,comp;
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] ])
            {
                st.push(make_pair(nod, v[nod][i]));
                dfs(v[nod][i], nod);
                if(mini[ v[nod][i] ] >= idx[nod])
                {
                     a = 0;
                     b = 0;
                     comp++;
                     do{
                        a = st.top().x;
                        b = st.top().y;
                        st.pop();
                        sol[comp].push_back(b);
                     }while(a != nod && b != v[nod][i]);
                     sol[comp].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<<comp<<'\n';
    for(i = 1; i <= comp; i++)
    {
        for(j = 0; j < sol[i].size(); j++)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}