Cod sursa(job #2145784)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 27 februarie 2018 16:52:34
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define MAXN 10005

std::vector <std::vector <int>> M;
std::vector <int> G[1 + MAXN], emptyVec;
std::stack <std::pair<int, int>> S;
int depth[1 + MAXN], lowlink[1 + MAXN];
void writeComponent(int node){
    int ok = 1;
    M.push_back(emptyVec);
    while(ok){
        if(S.top().second == node) ok = 0;
        M.back().push_back(S.top().first);
        S.pop();
    }
    M.back().push_back(node);
}
void tarjan(int node, int fth){
    depth[node] = lowlink[node] = depth[fth] + 1;
    for(int i = 0; i < G[node].size(); i++){
        if(!depth[G[node][i]]){
            S.push({G[node][i], node});
            tarjan(G[node][i], node);
            lowlink[node] = std::min(lowlink[node], lowlink[G[node][i]]);
            if(lowlink[G[node][i]] >= depth[node]) writeComponent(node);
        }
        if(G[node][i] != fth) lowlink[node] = std::min(lowlink[node], depth[G[node][i]]);
    }
}

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");
    }

    return 0;
}