Cod sursa(job #1468618)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 august 2015 15:31:12
Problema Componente biconexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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]] < retlv[nod])
                retlv[nod] = retlv[G[nod][i]];
            else
            {
                nrComp++;
                while(stiva.top()!=nod)
                {
                    co[nrComp].push_back(stiva.top ());
                    stiva.pop();
                }
                co[nrComp].push_back(stiva.top());
            }
        }
        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);

    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;
}