Pagini recente » Cod sursa (job #2428138) | Cod sursa (job #2122669) | Cod sursa (job #1182602) | Cod sursa (job #278175) | Cod sursa (job #2376316)
#include <bits/stdc++.h>
#define int_pair std::pair <int, int>
#define MAXN 100005
int N, M;
std::vector <int> ADC[MAXN];
std::vector <std::vector <int>> Biconex;
inline void AddEdge(int X, int Y) {
ADC[X].push_back(Y);
ADC[Y].push_back(X);
}
int Discovery[MAXN], Lowlink[MAXN];
int Time;
std::stack <int_pair> Edges;
void DFS(int Vertex = 1) {
Discovery[Vertex] = Lowlink[Vertex] = ++Time;
for (auto Edge:ADC[Vertex]) {
if (Discovery[Edge])
Lowlink[Vertex] = std::min(Lowlink[Vertex], Discovery[Edge]);
else {
Edges.push({Vertex, Edge});
DFS(Edge);
Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);
if (Discovery[Vertex] <= Lowlink[Edge]) {
Biconex.push_back(std::vector <int> ());
while (Edges.top().first != Vertex)
Biconex.back().push_back(Edges.top().second),
Edges.pop();
Biconex.back().push_back(Edge);
Biconex.back().push_back(Vertex);
Edges.pop();
std::sort(Biconex.back().begin(), Biconex.back().end());
}
}
}
}
std::ifstream In ("dijkstra.in");
std::ofstream Out("dijkstra.out");
void Citire() {
In >> N >> M;
for (int i=1, X, Y; i<=M; ++i)
In >> X >> Y, AddEdge(X, Y);
}
void Rezolvare() {
for (int i=1; i<=N; ++i)
if (!Discovery[i])
DFS(i);
Out << Biconex.size() << '\n';
for (auto Component:Biconex) {
for (auto Vertex:Component)
Out << Vertex << ' ';
Out << '\n';
}
}
int main()
{
Citire();
Rezolvare();
return 0;
}