Cod sursa(job #2145750)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 27 februarie 2018 16:35:12
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define MAXN 100010

std::vector <std::vector<int>> M;
std::vector <int> G[1 + MAXN], BC;
int st[1 + MAXN], inst[1 + MAXN], last, pos[1 + MAXN];
int lowlink[1 + MAXN], seen[1 + MAXN];
int cnt;
void tarjan(int node, int fth){
    //st[++last] = node; inst[node] = 1;
    pos[node] = lowlink[node] = pos[fth] + 1;
    seen[node] = 1;
    for(auto y: G[node]){
        if(!seen[y]){
            tarjan(y, node);
            lowlink[node] = std::min(lowlink[node], lowlink[y]);
            if(lowlink[y] >= pos[node]){
                cnt++;
                /*BC.clear();
                while(last > pos[node]){
                    BC.push_back(st[last]);
                    inst[st[last]] = 0;
                    last--;
                }
                BC.push_back(node);
                M.push_back(BC);*/
            }
        }
        if(y != fth) lowlink[node] = std::min(lowlink[node], pos[y]);
    }
}

int main(){
    FILE*fi,*fo;
    fi = fopen("biconex.in","r");
    fo = fopen("biconex.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        int a, b;
        fscanf(fi,"%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    tarjan(1, 0);
    /*fprintf(fo,"%d\n", M.size());
    for(int i = 0; i < M.size(); i++){
        for(auto j: M[i]) fprintf(fo,"%d ", j);
        fprintf(fo,"\n");
    }*/
    fprintf(fo,"%d", cnt);

    return 0;
}