Cod sursa(job #1383443)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 10 martie 2015 10:49:19
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#define MX 100001
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector<int> v[MX], d;
bool viz[MX];
int parent[MX], disc[MX], low[MX], total, act;

void Biconex(int i, int t)
{
    vector<int>::iterator it;

    viz[i] = 1;
    disc[i] = low[i] = act;
    act++;
    for(it=v[i].begin(); it!=v[i].end(); it++)
    {
        if(*it != t && disc[*it] < disc[i])
        {
            //adaugare in stiva
        }

        if(!viz[*it])
        {
            Biconex(*it, i);
            low[i] = min(low[i], low[*it]);

            if(low[*it] >= disc[i])
            {
                //afisare tot
                total++;
            }
            /*else
            if(*it != t)
            {
                low[i] = min(low[i], disc[*it]);
            }*/
        }
        else
        if(*it != t)
        {
            low[i] = min(low[i], disc[*it]);
        }
    }
}

int main()
{
    int i,x,y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            //total++;
            Biconex(i, 0);
        }
    }

    fout<<total;

    fin.close(); fout.close();
    return 0;
}