Cod sursa(job #2720620)

Utilizator sichetpaulSichet Paul sichetpaul Data 11 martie 2021 08:17:59
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int N, M, K;
int dp[Nmax], h[Nmax];
bool vis[Nmax];
vector<int> G[Nmax], ans[Nmax], nodes;

void MakeComp(int node) {
    ++K;
    for (auto it: nodes)
        ans[K].push_back(it);
    ans[K].push_back(node);
    nodes.clear();
}
void DFS(int node, int father) {
    vis[node] = 1;
    h[node] = dp[node] = h[father] + 1;

    for (auto it: G[node])
        if (vis[it] == 0) {  ///son
            DFS(it, node);
            dp[node] = min(dp[node], dp[it]);
            if (dp[it] >= h[node]) MakeComp(node);
        }
        else if (it != father) dp[node] = min(dp[node], h[it]); ///back-edge

    nodes.push_back(node);
}
int main()
{
    fin >> N >> M;
    while (M--) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1, 0);

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

    return 0;
}