Cod sursa(job #2003262)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 22 iulie 2017 15:30:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define MAXN 100000

std::vector <int> g[MAXN + 1];
bool viz[MAXN + 1];
int lvl[MAXN + 1];
int low[MAXN + 1];

std::stack <int> stk;
std::vector <int> sol[MAXN + 1];
int cnt = 0;

void dfs(int nod) {
    viz[nod] = 1;
    stk.push(nod);
    for(auto it : g[nod])
      if(viz[it] == 0) {
         lvl[it] = lvl[nod] + 1;
         low[it] = lvl[nod] + 1;
         dfs(it);
         if(low[it] >= lvl[nod]) {
            cnt++;
            while(stk.top() != it) {
                sol[cnt].push_back(stk.top());
                stk.pop();
            }
            stk.pop();
            sol[cnt].push_back(it);
            sol[cnt].push_back(nod);
         }
         low[nod] = std::min(low[nod], low[it]);
      }
      else
         low[nod] = std::min(low[nod], lvl[it]);
}


int main() {
    FILE *fi, *fout;
    int i, n, m, x, y;
    fi = fopen("biconex.in" ,"r");
    fout = fopen("biconex.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&m);
    for(i = 1; i <= m; i++) {
        fscanf(fi,"%d %d " ,&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i = 1; i <= n; i++)
        if(viz[i] == 0)
           dfs(i);
    fprintf(fout,"%d\n" ,cnt);
    for(i = 1; i <= cnt; i++) {
        for(auto it : sol[i])
            fprintf(fout,"%d " ,it);
        fprintf(fout,"\n");
    }
    fclose(fi);
    fclose(fout);
    return 0;
}