Cod sursa(job #1468652)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 august 2015 16:42:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

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

int n,m,nrComp,viz[100001],retlv[100001];
stack<int> stiva;
vector<int> co[100001];
vector<int> G[100001];

int DFS(int nod,int level)
{
    stiva.push(nod);
    viz[nod]=level; retlv[nod] = level;
    for(int i=0;i<G[nod].size();i++)
        if(viz[G[nod][i]] == 0)
        {
            DFS(G[nod][i],level+1);
            if(retlv[G[nod][i]] < level)
            {
                if(retlv[nod] > retlv[G[nod][i]])
                    retlv[nod] = retlv[G[nod][i]];
            }
            else
            {
                nrComp++;
                while(stiva.top()!=G[nod][i])
                {
                    co[nrComp].push_back(stiva.top ());
                    stiva.pop();
                }
                co[nrComp].push_back(stiva.top());
                stiva.pop();
                co[nrComp].push_back(nod);
            }
        }
        else
            if(retlv[nod] > retlv[G[nod][i]] && viz[G[nod][i]]!=level-1)
                retlv[nod] = retlv[G[nod][i]];
}

int main()
{
    int nod1,nod2;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>nod1>>nod2;
        G[nod1].push_back(nod2);
        G[nod2].push_back(nod1);
    }

    DFS(1,1);

    if(stiva.size()>1)
    {
        nrComp++;
        while(!stiva.empty())
        {
            co[nrComp].push_back(stiva.top());
            stiva.pop();
        }
    }

    int j;
    fout<<nrComp<<'\n';
    for(int i=1;i<=nrComp;i++)
    {
        sort(co[i].begin(),co[i].end());
        for(j=0;j<co[i].size();j++)
            fout<<co[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}