Cod sursa(job #1165809)

Utilizator dumytruKana Banana dumytru Data 2 aprilie 2014 22:24:22
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>

#define nmax 100000

using namespace std;

vector<vector<int> > graf,cc;
vector<int> isVisited,temp;
vector<pair<int,int> >nodes;
int n,m,k,nn[nmax+1],low[nmax+1];

int minmin(int a,int b)
{
    if(a<=b)return a;
    return b;
}

void getcc()
{
    //needs to be changes
    temp.push_back(nodes[0].first);
    for(int i=0;i<nodes.size();i++)
        temp.push_back(nodes[i].second);
    cc.push_back(temp);
    temp.clear();
    nodes.clear();
}

void DFS(int CN,int nivel)
{
    unsigned i;
    nn[CN]=low[CN]=nivel;
    for(i=0;i<graf[CN].size();i++)
    {
        if(graf[CN][i]==CN)continue;
        if(nn[graf[CN][i]]==0)
        {
            DFS(graf[CN][i],nivel+1);
            nodes.push_back(make_pair(CN, graf[CN][i]));
            low[CN]= minmin(low[CN],low[graf[CN][i]]);
            if(low[graf[CN][i]]>=nn[CN])
                getcc();
        }
        else
        {
            low[CN]= minmin(low[CN],nn[graf[CN][i]]);
        }
    }
}

int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    int i,u,v;
    f>>n>>m;
    graf.resize(n+1);
    isVisited.resize(n+1);
    for(i=1;i<=m;i++)
    {
        f>>u>>v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    DFS(1,1);
    g<<cc.size()<<'\n';
    /*
    for(i=0;i<cc.size();++i)
    {
        for(int j=0;j<cc[i].size();j++)
            cout<<cc[i][j]<<' ';
        cout<<'\n';
    }
    */
    return 0;
}