Pagini recente » Cod sursa (job #2250462) | Cod sursa (job #1348209) | Cod sursa (job #2705374) | Cod sursa (job #61173) | Cod sursa (job #1978871)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <stack>
using namespace std;
#ifdef INFOARENA
#define ProblemName "biconex"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
#define MAXN 100010
vector<int> G[MAXN];
vector<int> ccmp[MAXN];
stack<int> S;
int ccnr = 0;
int dpth[MAXN], lowp[MAXN];
void makeComp(int nod) {
while (!S.empty()) {
int t = S.top();
ccmp[ccnr].push_back(t);
if (t == nod) break;
S.pop();
}
++ccnr;
}
void DFS(int nod, int parent, int level) {
dpth[nod] = level;
lowp[nod] = dpth[nod];
S.push(nod);
for (const auto &it : G[nod]) {
if (dpth[it] >= 0) {
if (it != parent)
lowp[nod] = min(lowp[nod], dpth[it]);
continue;
}
DFS(it, nod, level + 1);
lowp[nod] = min(lowp[nod], lowp[it]);
if (lowp[it] >= dpth[nod])
makeComp(nod);
}
}
void printComps() {
printf("%d\n", ccnr);
for (int i = 0; i < ccnr; ++i) {
for (const auto &j : ccmp[i])
printf("%d ", j + 1);
putchar('\n');
}
}
void input() {
int N, M;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a, --b;
G[a].push_back(b);
G[b].push_back(a);
}
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
memset(dpth, 0xFF, sizeof(dpth));
input();
DFS(0, -1, 0);
printComps();
return 0;
}