Cod sursa(job #2461297)

Utilizator sichetpaulSichet Paul sichetpaul Data 25 septembrie 2019 12:45:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define Nmax 100005
#define pi pair<int, int>
#define pb push_back
#define mp make_pair
using namespace std;

   ifstream f("biconex.in");
   ofstream g("biconex.out");

int N, M, C, curr;
int lev[Nmax], best[Nmax];  //dfn si low
vector <int> graph[Nmax], ans[Nmax], comp;
bool vis[Nmax], done[Nmax];

void DFS(int node, int father) {
    vis[node] = 1;
    lev[node] = best[node] = lev[father] + 1;
    comp.pb(node);

  for (auto it: graph[node])

     if (vis[it] == 0) {
        DFS(it, node);
        best[node] = min(best[node], best[it]);

      if (best[it] >= lev[node]) {   //componenta biconexa
            ++C;
            ans[C].pb(node);
            while (comp.back() != it) {
                 ans[C].pb(comp.back());
                 comp.pop_back();
            }
            ans[C].pb(it), comp.pop_back();
      }
     }
     else if (it != father) best[node] = min(best[node], lev[it]);
}
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y;
        f >> x >> y;
        graph[x].pb(y);
        graph[y].pb(x);
    }

    DFS(1, 0);

   g << C << '\n';
    for (int i = 1; i <= C; ++i) {
        for (auto it: ans[i])
              g << it << " ";
        g << "\n";
    }

    return 0;
}