Cod sursa(job #2799363)

Utilizator robee1Chitu Robert-Alexandru robee1 Data 13 noiembrie 2021 04:44:27
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> muchii[100001];
bool verif[100001];
vector <int> cost(100001, 0);
vector <int> low(100001, 0);
vector <int> parent(100001, NULL);
int cont=0;
int time=0;
int n,m,x,y;
void AP(int v){
    verif[v]=true;
    time++;
    low[v]=time;
    cost[v]=time;
    int child=0;
    for (int i=0; i<muchii[v].size();i++){
            if(!verif[muchii[v][i]]){
                child++;
                parent[muchii[v][i]]=v;
                AP(muchii[v][i]);
                low[v]= min(low[v],low[muchii[v][i]]);
                if (parent[v]==NULL && child > 1)
                    cont++;
                if(parent[v]!=NULL && low[muchii[v][i]] >= cost[v])
                    cont++;

            }
            else if (muchii[v][i] != parent[v])
                low[v] = min(low[v], cost[muchii[v][i]]);

        }

}

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

AP(1);
g<<cont+1;
    return 0;
}