Cod sursa(job #2799360)

Utilizator robee1Chitu Robert-Alexandru robee1 Data 13 noiembrie 2021 03:49:42
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> cost(100001, 1000000);
vector <int> low(100001, 10000000);
bool verif[100001];
vector <int> muchii[100001];
int n,m,x,y,ant;
int counter=0;
void dfs(int nod){
    verif[nod]=true;
    counter++;
    cost[nod]=counter;
    low[nod]=counter;
    for (int i=0; i<muchii[nod].size();i++){
        int vecin = muchii[nod][i];
        if(verif[vecin]!=true)
            dfs(vecin);}
}
void lw(int nod){
    int flag=0;
    for (int i=0;i<muchii[nod].size();i++){
        int vecin=muchii[nod][i];
        if(cost[vecin]+1==cost[nod])
        flag=1;}
    for (int i=0;i<muchii[nod].size();i++){
        int vecin=muchii[nod][i];
        if(cost[vecin]<cost[nod] && (cost[nod]-1)!=cost[vecin] && flag==1)
            low[nod]=cost[vecin];

    }
}
int main()
{
    int cont=0;
    f>>n>>m;
    for (int i=1; i<=m;i++)
    {
        f>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
for (int i=1;i<=n;i++){
    if (verif[i]!=true){
        counter=0;
        dfs(i);
        }
}

for (int i=1;i<=n;i++){
        lw(i);

}
for (int i=n;i>=1;i--){
        if(low[i-1]>low[i])
            low[i-1]=low[i];

}
for (int i=1;i<=n;i++){
 for(int j=0; j<muchii[i].size();j++)
 {
     //cout<<muchii[n][j]<<" ";
     if(cost[i]<=low[muchii[i][j]])
     {
         cout<<cost[i]<<" ";
         cont++;
         break;
     }
 }

}
g<<cont+1;
    return 0;
}