Mai intai trebuie sa te autentifici.
Cod sursa(job #2321858)
Utilizator | Data | 16 ianuarie 2019 18:36:17 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.61 kb |
#include <bits/stdc++.h>
#define MAXN 100005
#define int_pair std::pair <int, int>
int N, M, NBicnx;
std::vector <int> ADC[MAXN], Bicnx[MAXN];
inline void AddEdge(int x, int y) {
ADC[x].push_back(y);
ADC[y].push_back(x);
}
std::ifstream In("biconex.in");
std::ofstream Out("biconex.out");
std::stack <int_pair> Stack;
int LVL[MAXN], Low[MAXN], Steps;
void DFS(int Vertex) {
LVL[Vertex] = Low[Vertex] = ++Steps;
for (auto Vecin:ADC[Vertex]) {
if (!LVL[Vecin]) {
Stack.push(mp(Vertex, Vecin));
DFS(Vecin);
Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);
if (Low[Vecin] >= LVL[Vertex]) {
while (Stack.top().first != Vertex)
Bicnx[NBicnx].push_back(Stack.top().second),
Stack.pop();
Bicnx[NBicnx].push_back(Stack.top().first);
Bicnx[NBicnx].push_back(Stack.top().second);
Stack.pop();
std::sort(Bicnx[NBicnx].begin(), Bicnx[NBicnx].end());
++ NBicnx;
}
}
else Low[Vertex] = std::min(Low[Vertex], LVL[Vecin]);
}
}
void Citire() {
In >> N >> M;
for (int i=0, x, y; i<M; ++i)
In >> x >> y, AddEdge(x, y);
}
void Rezolvare() {
for (int i=1; i<=N; ++i)
if (!LVL[i])
DFS(i);
Out << NBicnx << '\n';
for (int i=0, j; i<NBicnx; ++i, Out << '\n')
for (j=0; j<Bicnx[i].size(); ++j)
Out << Bicnx[i][j] << ' ' ;
}
int main()
{
Citire();
Rezolvare();
return 0;
}